为什么一般hashtable的桶数会取一个素数

什么一般Hashtable的桶数会取一个素数

假如有一个哈希函数:H(c) = c % N;

当N取一个合数时,最简单的例子是取2^n,比如说取2^3=8,这时候

H(11100(二进制)) = H(36) = 4
H(10100(二进制)) = H(28) = 4

这时候c的二进制第4位(从右向左数)就”失效”了,也就是说,无论第c的4位取什么值,都会导致H(c)的值一样.这时候c的第四位就根本不参与H(c)的运算,这样H(c)就无法完整地反映c的特性,增大了导致冲突的几率.

取其他合数时,都会不同程度的导致c的某些位”失效”,从而在一些常见应用中导致冲突.

在实际中往往关键字有某种规律,例如大量的等差数列,那么公差和模数不互质的时候发生碰撞的概率会变大,而用质数就可以很大程度上回避这个问题。基本可以保证c的每一位都参与H( c )的运算,从而在常见应用中减小冲突几率.

(个人意见:有时候不取质数效率也不会太差..但是无疑取质数之比较保险的..)

以上就是我的理解

补充一点,这里是说在常见应用中,往往有些数据会比较相近,这时候用质数比较好,比如要存放的数据是压缩的状态,比如存储一个描述当前搜索状态的表,的这时候哈希不用质数冲突机率就比较大。

如果是随机分布的整数,那么哈希模数只要取到足够大,在概率上来说都是一样的,但是这显然脱离实际应用。

你说的情况 是比较特殊的,因为选取了比较小的一个质数,当选去大质数N时,就可以仅在N进制的某一位失效,结合计算机系统的特性,N进制位表示法往往是不关键的,而常用的2^N进制比较关键,所以可以避免冲突。

其实,偶用一些大数做过测试,用来存放一个压缩为二进制的邻接矩阵,当模数足够大时,即便是合数也能有很接近质数的效果,但在某些(几十个)合数上会造成效率严重下降,所以质数是比较保险的。

你不妨自己做实验,不要去选随机整数,而要考虑一些常见应用,用质数和合数进行测试,主要考察平均装载因子,你得到的结论可能和我一样:合数绝大多数时候效果也不错,但在一部分合数上效果差得出奇,而质数几乎全部都有很好的效果。

我个人认为更普遍意义的理解,如果不取素数的话是会有一定危险的,危险出现在当假设所选非素数m=x*y,如果需要hash的key正好跟这个约数x存在关系就惨了,最坏情况假设都为x的倍数,那么可以想象hash的结果为:1~y,而不是1~m。但是如果选桶的大小为素数是不会有这个问题。

Hash碰撞冲突

我们知道,对象Hash的前提是实现equals()hashCode()两个方法,那么HashCode()的作用就是保证对象返回唯一hash值,但当两个对象计算值一样时,这就发生了碰撞冲突。如下将介绍如何处理冲突,当然其前提是一致性hash。

1.开放地址法

开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)
其中,m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1,称线性探测再散列。
如果di取1,则每次冲突之后,向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,…kk,-kk(k<=m/2),称二次探测再散列。
如果di取值可能为伪随机数列。称伪随机探测再散列。

2.再哈希法

当发生冲突时,使用第二个、第三个、哈希函数计算地址,直到无冲突时。缺点:计算时间增加。
比如上面第一次按照姓首字母进行哈希,如果产生冲突可以按照姓字母首字母第二位进行哈希,再冲突,第三位,直到不冲突为止

3.链地址法(拉链法)

将所有关键字为同义词的记录存储在同一线性链表中。

优点:

①拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;
②由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;
③开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;
④在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表,删除结点不能简单地将被删结 点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。

缺点:

指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。

4.建立一个公共溢出区

假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表,另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。

为什么hashtable桶数通常会取一个素数?如何有效避免hash结果值的碰撞
为什么一般hashtable的桶数会取一个素数

  • qq_43638135
    妲己再美究为妃: 博主没有想过自己接一些私活干吗?我现在还没毕业,但是我也确实听说外挂市场自动化游戏脚本市场挺火热的,并且报酬也很丰厚,但是具体的我也不是很清楚,求解答。 (1个月前 #47楼) 查看回复(2) 举报 回复
    22