關于hashcode 裡面 使用31 系數的問題

首先我們來了解一下hashcode，什麼是hashcode？有什麼作用？

hashcode其實就是散列碼，使用hashcode使用高效率的雜湊演算法來定位查找對象！

我們在使用容器來存儲資料的時候會計算一串散列碼，然後将資料放入容器。

如：string s =“java”,那麼計算機會先計算散列碼，然後放入相應的數組中，數組的索引就是從散列嗎計算來的，然後再裝入數組裡的容器裡，如list.這就相當于把你要存的資料分成了幾個大的部分，然後每個部分存了很多值， 你查詢的時候先查大的部分，再在大的部分裡面查小的，這樣就比先行查詢要快很多！

<a></a>

一個對象的hashcode就是一個簡單的hash算法的實作,雖然它和那些真正的複雜的！hash算法相比還不能叫真正的算法,但如何實作它,不僅僅是程式員的程式設計水準問題, 而是關系到你的對象在存取時性能的非常重要的問題.有可能,不同hashcode可能 會使你的對象存取産生成百上千倍的性能差别！

java string在列印這個類型的執行個體對象的時候總是顯示為下面的形式

test.test$tt@c17164

上面test.test是類名$tt是我自己寫的内部類，而@後面這一段是什麼呢？他其實就是tt這個執行個體類的hashcode是的16進制！

它使用了object 裡面的tostring()方法

java代碼

return getclass().getname() + “@” + integer.tohexstring(hashcode()); 

繼續看看java裡 string hashcode的源碼：

public int hashcode() {

int h = hash;

int len = count;

if (h == 0 &amp;&amp; len &gt; 0) {

int off = offset;

char val[] = value;

for (int i = 0; i &lt; len; i++) {

h = 31*h + val[off++];

}

hash = h;

return h;

} 

其實上面的實作也就是數學裡：

s[0]31^(n-1) + s[1]31^(n-2) + … + s[n-1] 

的實作！我們會注意那個狗血的31這個系數為什麼總是在裡面乘來乘去？為什麼不适用32或者其他數字？

大家都知道，計算機的乘法涉及到移位計算。當一個數乘以2時，就直接拿該數左移一位即可！選擇31原因是因為31是一個素數！

所謂素數：

質數又稱素數

。指在一個大于1的自然數中，除了1和此整數自身外，沒法被其他自然數整除的數。

素數在使用的時候有一個作用就是如果我用一個數字來乘以這個素數，那麼最終的出來的結果隻能被素數本身和被乘數還有1來整除！如：我們選擇素數3來做系數，那麼3*n隻能被3和n或者1來整除，我們可以很容易的通過3n來計算出這個n來。這應該也是一個原因！

在存儲資料計算hash位址的時候，我們希望盡量減少有同樣的hash位址，所謂“沖突”。如果使用相同hash位址的資料過多，那麼這些資料所組成的

hash鍊就更長，進而降低了查詢效率！是以在選擇系數的時候要選擇盡量長的系數并且讓乘法盡量不要溢出的系數，因為如果計算出來的hash位址越大，所

謂的“沖突”就越少，查找起來效率也會提高。

31可以 由i*31== (i&lt;&lt;5)-1來表示，現在很多虛拟機裡面都有做相關優化，使用31的原因可能是為了更好的配置設定hash位址，并且31隻占用5bits！

在java乘法中如果數字相乘過大會導緻溢出的問題，進而導緻資料的丢失.

而31則是素數（質數）而且不是很長的數字，最終它被選擇為相乘的系數的原因不過與此！

<a href="http://www.cogs.susx.ac.uk/courses/dats/notes/html/node114.html" target="_blank">http://www.cogs.susx.ac.uk/courses/dats/notes/html/node114.html</a>

本文來源于"阿裡中間件團隊播客",原文發表時間" 2012-03-19"