为双散列哈希表大小选择的最佳素数是什么?
辅助信息
- 哈希表是单词分析项目、马尔可夫模型、训练机器人建模和生成文本的一部分,就好像其他人会写它一样(这需要大量单词、句子、成绩单、书籍……越大) 语料库,更好)
- 我不熟悉有关素数的大部分数学知识,但我会阅读你们提出的所有内容,然后尝试从那里开始
我的想法:
- 素数不应该彼此太远/太近 ----> 我不必经常增加大小,但哈希表不会最终变成半空(更少的冲突,寻找负载因子和哈希表大小之间的理想比率)
- 对于大语料库来说是最佳的 - 我不确定我必须选择的素数应该有多大,以前从未这样做过......
- 我还考虑过实现一个函数(不是哈希函数),该函数只需将哈希表的大小加倍,然后查找最接近的素数 ------> 但它的运行时间为 O(n),因为素数只能被自身整除 ____( 我必须检查当前哈希表大小的两倍以内的所有数字是否有除零以外的余数,然后将大小增加一/转到下一个奇数并再次测试整个循环)________ ------> 你可以想象这会非常慢,所以更好的方法就是拥有一组固定的素数数量最多可达一百万(仅用于说明目的)左右,然后将它们用于任何尺寸更改
谢谢,如有任何其他问题,欢迎提问
最佳答案
选择 twin prime 的最高数字岛e.当p
和p - 2
是素数时,选择p
作为双倍哈希容量,因为hash_code % (size - 2)
code> 是双散列算法的一个很好的二级步骤函数,模素数比模合数更“稳健”(如果 size - 2
是合数)。
对于小尺寸(大约 1000 左右),选择所有素数,除了孪生对的低素数,因为孪生对在自然数的开头太罕见规模,以获得良好的尺寸可预测性。
添加 5 和 11 的大小(尽管它们在孪生素数中较低),以更好地解决非常小的表大小。
排除乘法哈希函数中经常使用的数字,在Java中,String
哈希函数中使用的是31
,我不了解Python。
以上所有内容均在此 Java 可运行程序中仔细编码,其中包含大量预先生成的表大小(尝试在相邻表大小之间保持 0.005 的最大差异):
P。 S. 我个人的信念是,双重散列永远不是最佳的开放寻址方式,因为现代 CPU 中的模运算成本过高。考虑使用QHash .
关于python - 为双散列哈希表大小选择最佳素数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32918254/