1

为双散列表大小选择的最佳素数是什么？

侧面信息

  • 哈希表是单词分析项目的一部分，马尔可夫模型，训练机器人来建模和生成文本，就好像其他人会写一样（这需要很多单词、句子、成绩单、书籍……语料库越大，更好的）
  • 我不熟悉围绕素数的大部分数学，但我会阅读你们提出的所有建议，然后尝试从那里开始

我的想法是：

  • 素数不应该太远/彼此接近---->我不必经常增加大小，但哈希表最终不会半空（更少的冲突，寻找理想的比例负载因子和哈希表大小）
  • 最适合大型语料库 - 我不确定我必须选择的素数应该有多大，以前从未这样做过......
  • 我还想过实现一个函数（不是哈希函数），它只是将哈希表的大小加倍，然后寻找最接近的素数 ------> 但它的运行时间为 O(n)因为素数只能被自身整除____（我必须检查直到当前哈希表大小的两倍的所有数字是否具有除零以外的余数，然后将大小加一/转到下一个奇数并再次测试整个循环）________ ------> 您可以想象这会非常慢，因此更好的方法是使用一组固定的素数，最多可达一百万（仅用于说明目的）左右，然后将它们用于任何尺寸更改

谢谢，任何其他问题表示赞赏

4

2 回答 2

2

选择双素数中的高位，即当和是素数时，选择作为双哈希容量，因为对于双哈希算法来说是一个很好的二级阶跃函数，并且模素数比模合数更“稳健”（如果是复合数） .pp - 2phash_code % (size - 2)size - 2

对于小尺寸（大约 1000 左右），选择所有素数，除了双胞胎中的低素数，因为双胞胎在自然数尺度开始时太少了，无法获得良好的尺寸可预测性。

添加大小 5 和 11（尽管它们的孪生素数较低）以更好地处理非常小的表大小。

排除乘法散列函数中经常使用的数字，在Java31中是散列函数中使用的数字String，我不了解Python。

以上所有内容都在这个 Java 可运行文件中仔细编码，具有许多预先生成的表大小（试图保持相邻表大小之间的最大差异为 0.005）：

https://github.com/OpenHFT/Koloboke/blob/0498951705b45be2e1528afd786c03308c36e5dc/lib/impl/src/main/java/net/openhft/koloboke/collect/impl/hash/DHashCapacities.java#L255-L272

PS 我个人认为，双重哈希绝不是最佳的开放寻址方式，因为模运算在现代 CPU 中成本过高。考虑使用QHash。

于 2015-10-03T05:30:39.420 回答
1

不确定我是否完全理解你的问题，但这里有一个来自 java world 的可能解决方案。如果您必须从头开始编写散列函数，我理解为什么通常需要素数，但不确定如果使用像这样的“好”散列函数，您是否需要研究它们。

希望这可以帮助！

于 2015-10-03T02:26:27.483 回答