亲宝软件园·资讯

展开

hashtable桶数 hashtable桶数通常会取一个素数分析

人气:0
想了解hashtable桶数通常会取一个素数分析的相关内容吗,在本文为您仔细讲解hashtable桶数的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:hashtable桶数,hashtable桶数分析,hashtable桶数素数,下面大家一起来学习吧。

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

设有一个哈希函数

H( c ) = c % N;

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

H( 11100(二进制) ) = H( 28 ) = 4
H( 10100(二进制) ) = H( 20 )= 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。但是如果选桶的大小为素数是不会有这个问题。

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

加载全部内容

相关教程
猜你喜欢
用户评论