1998年南开大学 · 哈希表 · 考研题

设a、b、c、d和e这5个字符的编码分别为1、2、3、4和5,并设标识符依以下次序出现ac、bd、aa、be、ab、ad、cd、bc、ae和cd。要求用哈希(Hash)方式将它们存放在具有10个位置的表中。

① 对上述关键字(标识符)构造一个哈希函数,使得发生冲突尽可能地少。

② 用线性探测再散列法解决冲突。

写出上述各关键字在表中的位置。

答案

① 设计哈希函数 H(xy)=(3x+y) mod 10,其中x表示首字母的编号,y表示末字母的编号。利用这个哈希函数,可以将10个关键字散列到具有10个位置的表中,冲突共一次。

② 

address0123456789
keybdbececdaaabacadaebc


笔记