Java中HashCode算法詳解
Java中的集合，比如HashMap/HashSet/HashTable在實現(xiàn)上都用到了hashCode算法，用來計算元素在數(shù)組中的位置毡代。hashCode是Object類中的一個方法，所以，所有的Java類都有這個方法苗沧，只是一些類對這個方法進行了覆寫，下面以String類的實現(xiàn)為例進行說明：
public int hashCode() {
????int h =hash;
? ? if (h ==0 &&value.length >0) {
????????char val[] =value;
? ? ? ? for (int i =0; i <?value.length; i++) {
????????h =31 * h + val[i];
? ? ? ? }
????????hash = h;
? ? }
????return h;
}
其實這個算法的實現(xiàn)很簡單炭晒，以“hangzhou”這個字符串為例待逞，計算過程如下：
第一步：int ‘h’
第二步：31 * （第一步結(jié)果） + int ‘a(chǎn)’
第三步：31 * （第二部結(jié)果） + int ‘n’
第四步：31 * （第三步結(jié)果） + int ‘g’
第五步：31 * （第四步結(jié)果） + int ‘z’
第六步：31 * （第五步結(jié)果） + int ‘h’
第七步：31 * （第六步結(jié)果） + int ‘o’
第八步： 31 * （第七步結(jié)果） + int ‘u’
可以得到“hangzhou”的hashcode為4740586。
為什么HashMap中的&位必須位奇數(shù)（length-1）
從key映射到HashMap數(shù)組的對應(yīng)位置需要一個Hash函數(shù)：
index = Hash("hangzhou")
如何實現(xiàn)一個盡量分布均勻的hash函數(shù)呢网严？我們使用key的hashcode做某種運算：
index = hashCode("hangzhou") & (Length - 1) 其中识樱，Length為HashMap的長度，下面來演示整個過程：
1震束、“hangzhou”的hashcode為4740586怜庸，二進制表示為100 1000 0101 0101 1110 1010
2、假定HashMap的長度為默認(rèn)的16垢村，則Length - 1為15割疾，也就是二進制的1111
3、把以上兩個結(jié)果做與運算肝断，得到的結(jié)果為1010杈曲，也就是index為10
可以說，Hash算法最終得到的index結(jié)果完全取決于hashCode的最后幾位胸懈。
假設(shè)担扑，HashMap的長度為10，則Length - 1為9趣钱，也就是二進制的1001涌献，通過Hash算法得到的最終index為8，當(dāng)只有一個元素的時候這沒問題首有。但是我們再來試一個hashCode：100 1000 0101 0101 1110 1110時燕垃，通過Hash算法得到的最終的index也是8枢劝，另外還有100 1000 0101 0101 1110 1000得到的index也是8。也就是說卜壕，即使我們把倒數(shù)第二您旁、三位的0、1變換轴捎，得到的index仍舊是8鹤盒，說明有些index結(jié)果出現(xiàn)的幾率變大！侦副！而有些index結(jié)果永遠不會出現(xiàn)侦锯，比如二進制0000.
這樣，顯然不符合Hash算法均勻分布的要求秦驯。
反觀尺碰，長度16或其他2的冪次方，Length - 1的值的二進制所有的位均為1译隘，這種情況下亲桥，Index的結(jié)果等于hashCode的最后幾位。只要輸入的hashCode本身符合均勻分布固耘，Hash算法的結(jié)果就是均勻的两曼。
一句話，HashMap的長度為2的冪次方的原因是為了減少Hash碰撞玻驻，盡量使Hash算法的結(jié)果均勻分布。
