hashtable - 使用哈希作为桶索引，模与位掩码

Question

我一直在研究哈希表，其中一些数据经过哈希处理并用于存储桶索引。

一些库使用哈希与存储桶大小的模，而其他库则使用位掩码。其中仅使用桶掩码使用的位(确保不超出范围)。

位掩码:

index = h->hash_func(key) & h->hash_mask;

取模:

index = h->hash_func(key) % h->bucket_tot;

虽然两者之间存在明显的差异，例如位掩码的存储桶大小限制，但确保散列在较低位上提供良好的分布、模数速度......等。

是否有充分的理由选择其中之一？

<小时/>

(我可能会尝试针对我自己的用例进行基准测试，但很好奇这件事上已知的内容)。

请注意，这仅适用于键:值存储(字典/散列/关联数组)，与安全无关。

使用位掩码动态调整大小、链接哈希表实现的示例:

• https://github.com/amadvance/tommyds/blob/master/tommyds/tommyhashdyn.c
• https://github.com/GNOME/glib/blob/master/glib/ghash.c

使用模数的示例:

• https://www.daniweb.com/software-development/c/threads/104887/sucinct-example-of-hash-table-w-chaining

Answer 1

您提到了“桶”索引，所以我假设您的意思是具有单独链接作为冲突解决方案的哈希表，在这种情况下，没有理由使用您提到的“更强”的模数或位掩码(顺便说一句，这并不那么明显，因为你说)。

在某些语言中，尤其是基于 Java/JVM 的语言，数组索引是带正号的 32 位整数，因此位掩码的最大数组大小为 2^30，这可能是不够的，也是使用 no-power 的充分理由-of-two 表大小和模数，使用它您可以非常接近 2^31-1(最大可能的有符号 32 位整数)。但由于您使用了 C++ 语法，因此您不必担心。

此外，如果您不仅意味着单独的链接，某些开放寻址冲突解决算法需要表大小满足某些条件，例如，如果您实现双散列，则表大小应为素数。在这种情况下，您显然应该仅使用模来获取表中的初始索引。