为什么 .Net 字典要调整大小为质数？

Question

根据这个问题，.Net字典将已分配的空间调整为至少是当前大小两倍的质数。使用质数而不仅仅是两倍于当前大小对于什么原因很重要？（我尝试运用我的谷歌技能找到答案，但是没有成功）

- maayank

---

作为对你问题的一个附加想法，有没有人知道一种树状平衡数据结构，可以调整大小到质数大小？也许我应该发另一个问题。 - costy.petrisor

.Net的字典背后使用了什么样的树形数据结构？ - costy.petrisor

我在这里提出了问题：http://stackoverflow.com/questions/4639122/balanced-tree-like-data-structure-that-resizes-to-prime-sizes - costy.petrisor

@costy 没有，这是一个哈希表而不是树。 - CodesInChaos

Answer 1

元素被放置的桶由 (hash & 0x7FFFFFF) % capacity 确定。这需要均匀地分布。由此可见，如果有多个条目是某个基数（hash1 = x1 * base，hash2 = x2 * base...）的倍数，并且 base 和 capacity 不互质（最大公约数>1），一些槽会被过度使用，而其他槽则永远不会被使用。由于除它们自己以外，质数与任何数都互质，因此它们相对而言很有可能实现良好分布。

其中一个特别好的属性是：capacity > 30 时每个位对哈希码的贡献是不同的。因此，如果哈希的变化仅集中在少量位上，它仍将导致良好的分布。这就解释了为什么二的幂容量是不好的：它们掩盖了高位。仅高位不同的数字集合并不那么不太可能出现。

我个人认为他们选择的函数很糟糕。它包含一个昂贵的模运算，如果条目是质数容量的倍数，则其性能会下降。但它似乎对于大多数应用程序来说已经足够好了。

- CodesInChaos

Answer 2

这是与选择好的哈希函数相关的算法实现细节，它提供了均匀分布。非均匀分布会增加碰撞的数量，并增加解决碰撞的成本。

- Darin Dimitrov

---

选择质数并不能提供均匀分布，不需要过于简化。当hashsize = prime_number时，与hashsize = 2^k或任何其他情况相比，发生碰撞的概率完全相同。只是某些哈希大小使碰撞看起来更加“不可预测”，“随机”或“均匀分布”。另一方面，当hashsize = 2^k时，基于异或的任何哈希函数都将表现不佳。 - Nikita Rybak

Answer 3

由于质数的数学特性，它们无法被分解成更小的数字。因此，当您将哈希值从存储项中除以时，您会得到一个均等的分布。如果没有质数，根据对象的不同，分布可能不均匀。

- TomTom