- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
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的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我在字符串中有一个大词。例子白 Wine 额外优惠。 我想在第一行使用“White”,在第二行使用“wine extra offer”。使用下面的代码: string value="White win
我想在无符号中执行一些算术运算,需要取负整数的绝对值,比如 do_some_arithmetic_in_unsigned_mode(int some_signed_value) { unsign
我正在努力使用 data.table 来总结向量函数的结果,这在 ddply 中很容易。 问题 1:使用带有矢量输出的(昂贵的)函数聚合 dt dt[ , as.list(quantile(x)),
我有两个分数列表; 说 A = [ 1/212, 5/212, 3/212, ... ] 和 B = [ 4/143, 7/143, 2/143, ... ] . 如果我们定义 A' = a[0] *
我已经使用 numpy 从 csv 文件中获取数据。 numpy 数组的尺寸为:100*20。我如何取列的平均值(比如 col 3,5,8)并用包含这 3 个 cols 平均值的新列替换它们 如果
在 Rust 中取任意数的 n 次根的最佳方法是什么?例如,num crate 只允许取整数类型的第 n 个主根,即 floor'ed 或 ceil'ed 值......如何最好地接近实际值? 最佳答
看起来这应该很容易,但我很困惑。我已经掌握了使用 dplyr 进行编程的大致技巧0.7,但为此苦苦挣扎:How do Iprogram in dplyr我想要编程的变量是否是一个字符串? 我正在抓取数
在 Rust 中取任意数的 n 次根的最佳方法是什么?例如,num crate 只允许取整数类型的第 n 个主根,即 floor'ed 或 ceil'ed 值......如何最好地接近实际值? 最佳答
我有一个 pandas 数据框,其中有一列名为“coverage”。对于一系列特定索引值,我想获取前 100 行的平均“覆盖率”值。例如,对于索引位置 1001,我想要第 901-1000 行的平均“
import pandas as pd data = {'date': ['1998-03-01', '2001-04-01','1998-06-01','2001-08-01','2001-05-0
我有一个包含 100 个数字的 NSArray。我想创建一个 5 个数字的 NSArray。第二个数组中的第一个数字是第一个数组中前 20 个数字的平均值。第二个数字是第一个数组中第二组 20 个数字
我该怎么做?我试过 abs() 但它只适用于整数。有内置的方法吗? CGFloat flo = -123; abs(flo) 返回 0 最佳答案 使用 fabs() CGFloat f = -123.
我正在采用以下计算的 log2: tl_out.a.bits.size := log2Ceil(s1_row * s2_column * 4.U) 其中,s1_row 和 s2_column 是 UI
如何从 m 个元素集合中取出 n 个元素,以便在元素用完时从头开始? List list = new List() {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; List newL
我已经完成了研究,但似乎找不到有关该主题的足够文档。 在 Object streams 上尝试一些代码时,我注意到将 BufferedOutputStream 放入 ObjectOutputStrea
我需要计算数据中连续时间组之间的差异,如下所示 from io import StringIO import pandas as pd strio = StringIO("""\
我在 Mongo 数据库中有以下文档: { _id: 1, question: "Blue or red?", __v: 0, votes: [9, 5] } 我想在后
好吧,宇宙中一定有人知道这个问题的答案。 我已经在这里问过这个问题,但仍然没有解决方案。 我需要保留和换行 div 中的文本。到目前为止,我很难想出解决方案。我找到的最佳解决方案并不适用于所有浏览器。
我正在尝试采用 3 个单独的整数输入(年、月、日)并采用这 3 个条目并从中形成一个日期对象,以便我可以使用它来比较其他日期。 这是我目前所拥有的,不知从何而来: public void compar
在我的 IOS 项目中,我有一个包含该函数的自定义 Logger 类(单例) - (void)log:(NSString *)domain logLevel:(int)level logMessage
我是一名优秀的程序员,十分优秀!