.net - 为什么 .Net 词典会调整为质数？

Question

根据 this question .Net 字典将其分配的空间大小调整为至少是当前大小两倍的素数。为什么使用质数而不是当前大小的两倍很重要？ (我试图用我的 google-fu 能力找到答案，但无济于事)

Answer 1

放置元素的桶由(hash & 0x7FFFFFF) % capacity决定。这个需要均匀分布。由此可知，如果多个条目是某个基数的倍数 (hash1 = x1 * base, hash2 = x2 * base,...) 其中 base 和 capacity 不是互质的(最大公约数 > 1)，有些槽被过度使用，有些槽从未使用过。由于质数与除自身以外的任何数互质，因此它们有相对较好的机会实现良好的分布。

它的一个特别好的特性是对于capacity > 30，每一位对哈希码的贡献是不同的。因此，如果哈希的变化仅集中在几个位上，它仍然会导致良好的分布。这解释了为什么是 2 的幂的容量是不好的:它们掩盖了高位。一组只有高位不同的数字不太可能。

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