1999年清华大学 · 哈希表 · 考研题

设有12个数据{25,40,33,47,12,66,72,87,94,22,5,58},它们存储在散列表中,利用双散列解决冲突,要求插入新数据的平均查找次数不超过3次。

① 该散列表的大小m应该设计多大?

② 试为该散列表设计相应的散列函数(用除留余数法)并计算寻找下一个“空位”时向前跨步步长的再散列函数。

③ 顺次将各个数据散列到表中。

④ 计算查找成功的平均查找次数。

提示

设计Hash表的步骤为:

(1)根据所选择的处理冲突的方法求出装载因子α的上界;

(2)由α值设计Hash表的长度m;

(3)根据关键字的特性和表长m选定合适的Hash函数。

答案

① 线性探测再散列的哈希表查找成功的平均查找长度为:

Sn=(1+1/(1-α))/2≤3

∴ α≤4/5  (α为填充因子)

即 12/m≤4/5,m≥15

不妨取m=16.

② 散列函数 H(key)=key mod 16

再散列函数 H(key)+3.

③ 形成的散列表为:

QQ截图20191129121228.png

④ 查找成功的平均查找次数为:

(1+1+...+1+2+1)/12=1.08

笔记