Java HashMap分析之二：Hash code
散列計算就是計算元素應該放在數組的哪個元素里。準確的說是放到哪個鏈表里面。按照Java的規則，如果你要想將一個對象放入HashMap中，你的對象的類必須提供hashcode方法，返回一個整數值。比如String類就有如下方法：
- public int hashCode() {
- int h = hash;
- int len = count;
- if (h == 0 && len > 0) {
- int off = offset;
- char val[] = value;
- for (int i = 0; i < len; i++) {
- h = 31*h + val[off++];
- }
- hash = h;
- }
- return h;
- }
注意上面的for循環，有點搞吧？我來舉個例子，讓你很容易明白它在搞什么名堂。比如有一個字符串“abcde”,采用31進制的計算方法來計算這個字符串的總和，你會寫出下面的計算式子：
a*31^4+b*31^3+c*31^2+d*31^1+e*31^0.注意，這里的a,b,c,d或者e指的是它們的ASCII值。很有趣的循環，居然可以用來算N進制。這個循環可以抽出來單獨作為計算進制的好工具：
- public static void main(String[] args) {
- int[] a={1,0};
- System.out.println(calculate(2,a));
- }
- private static int calculate(int radix,int[] a){
- int sum = 0;
- for(int i=0;i<a.length;++i){
- sum = sum*radix+a[i];
- }
- return sum;
- }
靜態方法caculate接受radix作為進制基數，數組a模擬要計算的進制的數字，只是注意表面順序需要一致。比如 01 二進制串，在數組中要按照{0,1}排列。上面的輸出結果是1，符合01的真實值。
那么為什么選用31作為基數呢？先要明白為什么需要HashCode.每個對象根據值計算HashCode,這個code大小雖然不奢求必須唯一（因為這樣通常計算會非常慢），但是要盡可能的不要重復，因此基數要盡量的大。另外，31*N可以被編譯器優化為
左移5位后減1，有較高的性能。其實選用31還是有爭議，反對者（參考http://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier）
認為這個東西還是會導致較多的重復，應該用更大的數字。所以，或許將來Java的實現中會有所變化。下面這篇文章介紹了兩個結論：
1.基數要用質數
質數的特性（只有1和自己是因子）能夠使得它和其他數相乘后得到的結果比其他方式更容易產成唯一性，也就是hash code值的沖突概率最小。
2.選擇31是觀測分布結果后的一個選擇，不清楚原因，但的確有利。
http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/
另外，String.hashCode內部會緩存第一次計算的值，因為這是一個final（不可變）類，也就是String對象的內容是不會變的。這能夠在多次put到HashMap的場合提高性能，不過似乎用處不多。
好了，終于扯完了String.hashCode的話題。現在繼續回到HashMap的數組元素位置計算上來。
原文鏈接：http://blog.csdn.net/sheismylife/article/details/7351005
【編輯推薦】
