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

根據this question .Net字典將其分配的空間大小調整爲至少是當前大小的兩倍的素數。爲什麼使用素數而不是當前大小的兩倍很重要？（我試圖用我的谷歌功夫找到答案，但無濟於事）爲什麼.Net字典調整爲素數？

來源

2011-01-09 maayank

作爲一個側面的想法給你的問題，有沒有人知道樹狀平衡的數據結構，調整到黃金大小？也許我應該發表另一個問題 – 2011-01-09 11:36:54

什麼是.Net的字典背後的樹數據結構呢？ – 2011-01-09 11:39:16

這是一個與choosing a good hashing function相關的算法實現細節，它提供了均勻分佈。不均勻分佈會增加碰撞次數和解決它們的成本。

來源

2011-01-09 09:38:40

由於質數的數學。他們不能被分解成不同的小數字。當您從存儲的項目中分散散列號碼時，您將獲得平均分配。如果您沒有素數，則取決於對象，分佈可能不均勻。

來源

2011-01-09 09:37:34 TomTom

放入元素的存儲桶由(hash & 0x7FFFFFF) % capacity決定。這需要均勻分佈。因此，如果多個條目是某個基數（hash1 = x1 * base,hash2 = x2 * base，...）的倍數，其中base和capacity不是互質（最大公約數> 1）用過的。由於素數與除自身以外的任何數字都是相互矛盾的，因此他們有較好的分配機會。

其中一個特別好的特性是，對於capacity > 30，每個位對散列碼的貢獻是不同的。所以如果散列的變化集中在只有幾位，它仍然會導致一個很好的分佈。這就解釋了爲什麼兩個冪的能力是不好的：它們掩蓋了高位。一組只有高位不同的數字並不是不太可能。

我個人認爲他們選擇這個功能不好。它包含一個昂貴的模操作，並且如果條目是總容量的倍數，則其性能會下降。但對大多數應用程序來說，它似乎已經足夠好了。

來源

2011-01-09 09:53:37 CodesInChaos

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

回答

相關問題