gpt4 book ai didi

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

转载 作者:qq735679552 更新时间:2022-09-29 22:32:09 24 4
gpt4 key购买 nike

CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章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。但是如果选桶的大小为素数是不会有这个问题.

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

原文链接:http://blog.csdn.net/liuqiyao_01/article/details/14475159 。

最后此篇关于hashtable桶数通常会取一个素数分析的文章就讲到这里了,如果你想了解更多关于hashtable桶数通常会取一个素数分析的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com