淨的GetHashCode位換檔操作

Question

我一直在尋找通過一些.NET源昨日，看到的GetHashCode的幾種實現，其中沿着這個線的東西：

(i1 << 5) + i^i2 

我明白代碼在做什麼，爲什麼。我想知道的是爲什麼他們使用（i1 < < 5）+ i而不是（i1 < < 5）- i。

我見過的大多數框架都使用-i，因爲這相當於乘以31，這是素數，但Microsoft方式相當於乘以33，因爲它有11和3因素，因此不是素數。

這是否有一個已知的理由？任何合理的假設？

Answer 1

我在math.stackexchange.com上問了同樣的問題：Curious Properties of 33。

數學家和我的話題做了研究中的猜想讓我相信答案是這樣的：

好吧，我發現了爲什麼微軟使用33這就是所謂的伯恩斯坦 哈希。事實證明，33有一些神奇的屬性，產生散列碼的良好分佈，並且關於爲什麼有很少的理論知識。

基本上，在熵和速度比較中，伯恩斯坦做得足夠好，而且非常活潑。丹·伯恩斯坦（Dan Bernstein）是一位33歲的人，他無法解釋33的屬性如何產生如此好的散列分佈。

有幾篇論文比較了散列函數，並且已經證實了這一發現，但沒有進一步解釋使用33的好處。此外，我找不到爲什麼Java使用31代替。迄今爲止，這似乎是一個數學和編程的謎團。

Answer 2

我不記得31是否是這些素數中的一個，但是有一些素數被Dictionary<K,V>用作容量。如果你使用左邊的字段不會影響選定的存儲桶，並且散列值會退化。