扫码获取更多资源

●哈希函数的构造

构造哈希函数的方法很多，但究竟什么是“好”的哈希函数呢？设计哈希函数一般应该 遵循以下两个原则：

（1） 简单：指哈希函数的计算简单快速。

（2） 均匀：指对于关键字集合中的任一关键字，哈希函数能够以等概率将其映射到哈 希表空间的任何一个位置上。也就是说，哈希函数能够将关键字集合K随机均匀地分布在 哈希表的地址集{O,l，・・・，m—l}_t,以使冲突最小化。

以上两个原则在实际应用中往往是矛盾的。为了保证哈希地址的均匀性较好，哈希函 数的计算就必然要复杂；反之，如果哈希函数的计算比较简单，则均匀性就可能较差。一般 来说，哈希函数依赖于关键字的分布情况，但在许多应用中，事先并不知道关键字的分布情 况，关键字有可能高度汇集（即分布得很差）。因此，在设计哈希函数时，要根据具体情况，选 择一个比较合理的方案。下面介绍几种常见的哈希函数。

直接定址法

基本思想

哈希函数是关键字的线性函数，由式（8-5）表示：

H（k） = aX k + b （a、b 为常数） （8-5）

例8-8 关键字集合为{10, 30, 50, 70, 80, 90},选取的哈希函数为H（k） = k/10,采 用直接定址法构造的哈希表如图8-35所示。

主要特点

直接定址法的特点是单调、均匀；由于直接定址所得地址集合和关键字集合的大小相 同，因此对于不同关键字不会发生冲突，但实际中能使用这种哈希函数的情况很少。它适用 于事先知道关键字的分布，且关键字集合不是很大而连续性较好的情况。

除留余数法

基本思想

选取关键字被某个不大于哈希表表长m的正整数p除后所得余数作为哈希地址，由 式（8-8）表示:

H（k）=kM（）Dp （8-6）

例8・9 关键字集合为{ 14, 21, 28, 35, 42, 49, 56},选取p = 21,采用除留余数法得到 的哈希地址如图8-36所示。

数字分析法

基本思想

根据关键字在各个位上的分布情况，选取分布比较均匀的若干位组成哈希地址。

例8-10 关键字如图8-37(a)所示。分析这组关键字发现，第①位数字全是1,第②位 数字集中在7、8、9上，第④位数字集中在0、1、2上，第⑥位数字集中在5、6、7上，因此这几 位分布不均匀，故不能选用；而第③、⑤、⑦位数字介于1〜9之间，分布较均匀，因此可以作 为哈希地址选用。如果哈希列地址是两位，则可以取这三位中的任意两位组合成哈希地址， 本例中选取第③、⑦位数字作为哈希地址，得到的哈希地址如图8-37(b)所示。

联系我们：