散列函数设计：除留余数法

客官°小女子只卖身不卖艺 2022-07-12 11:47 151阅读 0赞

散列函数设计：除留余数法  
[转载地址][Link 1]  
感谢分享

除留余数法介绍  
除留余数法此方法为最常用的构造散列函数方法。对于散列表长为m的散列函数公式为：

f( key ) = key mod p ( p ≤ m )

mod是取模（求余数）的意思。事实上，这方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。  
一个例子

很显然，本方法的关键就在于选择合适的p, p如果选得不好，就可能会容易产生同义词。下面我们来举个例子看看：

有一个关键字，它有12个记录，现在我们要针对它设计一个散列表。如果采用除留余数法，那么可以先尝试将散列函数设计为f(key) = key mod 12的方法。比如29 mod 12 = 5，所以它存储在下标为5的位置。  
![这里写图片描述][SouthEast]  
不过这也是存在冲突的可能的，因为12 = 2×6 = 3×4。如果关键字中有像18(3×6)、30(5×6)、42(7×6)等数字，它们的余数都为6，这就和78所对应的下标位置冲突了。

甚至极端一些，对于下图的关键字，如果我们让p为12的话，就可能出现下面的情况，所有的关键字都得到了0这个地址数，这未免也太糟糕了点。

![这里写图片描述][SouthEast 1]  
但是我们如果不选用p=12来做除留余数法，而选用p=ll，则结果如下：  
![这里写图片描述][SouthEast 2]  
这个时候就只有12和144有冲突，相对来说，就要好很多了。  
如何合理选取p值

使用除留余数法的一个经验是，若散列表表长为m，通常p为小于或等于表长（最好接近m)的最小质数或不包含小于20质因子的合数。
    
    这句话怎么理解呢？要不这样吧，我再举个例子：某散列表的长度为100，散列函数H(k)=k%P,则P通常情况下最好选择哪个呢？A、91 B、93 C、97 D、99
    实践证明，当P取小于哈希表长的最大质数时，产生的哈希函数较好。我选97，因为它是离长度值最近的最大质数。

[Link 1]: http://blog.csdn.net/wangpengqi/article/details/9714207
[SouthEast]: /images/20220710/dce325f7eefd4247a112657df74d82f3.png
[SouthEast 1]: /images/20220710/0987f3edcc674acea2627b5524950fa3.png
[SouthEast 2]: /images/20220710/7d6e61abd7bb416c881c943018ab0837.png