為什麼 .Net 字典調整為素數？

根據這個問題，.Net 字典將其分配的空間調整為至少是目前大小兩倍的素數。為什麼使用質數很重要，而不僅僅是目前大小的兩倍？（我試圖使用我的 google-fu 能力來尋找答案，但無濟於事）

它是與選擇一個好的散列函式相關的算法實現細節，它提供了均勻分佈。非均勻分佈會增加衝突的數量，以及解決它們的成本。

放置元素的桶由 決定(hash & 0x7FFFFFF) % capacity。這需要均勻分佈。由此可以得出，如果多個條目是某個基數 ( hash1 = x1 * base, hash2 = x2 * base,…)的倍數base並且capacity不是互質數（最大公約數 > 1），則某些插槽已被過度使用，而有些則從未使用過。由於素數與除它們自身之外的任何數互質，因此它們具有相對較好的實現良好分佈的機會。

一個特別好的特性是capacity > 30每個位對雜湊碼的貢獻是不同的。因此，如果散列的變化僅集中在幾個位上，它仍然會導致良好的分佈。這就解釋了為什麼容量是 2 的冪是不好的：它們掩蓋了高位。一組只有高位不同的數字並不是那麼不可能。

就我個人而言，我認為他們錯誤地選擇了該功能。它包含一個昂貴的模運算，如果條目是主要容量的倍數，它的性能就會崩潰。但這對於大多數應用程序來說似乎已經足夠了。

引用自：https://stackoverflow.com/questions/4638520