Java中HashCode算法詳解

Java中的集合，比如HashMap/HashSet/HashTable在實(shí)現(xiàn)上都用到了hashCode算法，用來計(jì)算元素在數(shù)組中的位置。hashCode是Object類中的一個(gè)方法，所以，所有的Java類都有這個(gè)方法，只是一些類對(duì)這個(gè)方法進(jìn)行了覆寫，下面以String類的實(shí)現(xiàn)為例進(jì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;

}

其實(shí)這個(gè)算法的實(shí)現(xiàn)很簡(jiǎn)單，以“hangzhou”這個(gè)字符串為例，計(jì)算過程如下：

第一步：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ù)組的對(duì)應(yīng)位置需要一個(gè)Hash函數(shù)：

index = Hash("hangzhou")

如何實(shí)現(xiàn)一個(gè)盡量分布均勻的hash函數(shù)呢？我們使用key的hashcode做某種運(yùn)算：

index = hashCode("hangzhou") & (Length - 1) 其中，Length為HashMap的長(zhǎng)度，下面來演示整個(gè)過程：

1、“hangzhou”的hashcode為4740586，二進(jìn)制表示為100 1000 0101 0101 1110 1010

2、假定HashMap的長(zhǎng)度為默認(rèn)的16，則Length - 1為15，也就是二進(jìn)制的1111

3、把以上兩個(gè)結(jié)果做與運(yùn)算，得到的結(jié)果為1010，也就是index為10

可以說，Hash算法最終得到的index結(jié)果完全取決于hashCode的最后幾位。

假設(shè)，HashMap的長(zhǎng)度為10，則Length - 1為9，也就是二進(jìn)制的1001，通過Hash算法得到的最終index為8，當(dāng)只有一個(gè)元素的時(shí)候這沒問題。但是我們?cè)賮碓囈粋€(gè)hashCode：100 1000 0101 0101 1110 1110時(shí)，通過Hash算法得到的最終的index也是8，另外還有100 1000 0101 0101 1110 1000得到的index也是8。也就是說，即使我們把倒數(shù)第二、三位的0、1變換，得到的index仍舊是8，說明有些index結(jié)果出現(xiàn)的幾率變大??！而有些index結(jié)果永遠(yuǎn)不會(huì)出現(xiàn)，比如二進(jìn)制0000.

這樣，顯然不符合Hash算法均勻分布的要求。

反觀，長(zhǎng)度16或其他2的冪次方，Length - 1的值的二進(jìn)制所有的位均為1，這種情況下，Index的結(jié)果等于hashCode的最后幾位。只要輸入的hashCode本身符合均勻分布，Hash算法的結(jié)果就是均勻的。

一句話，HashMap的長(zhǎng)度為2的冪次方的原因是為了減少Hash碰撞，盡量使Hash算法的結(jié)果均勻分布。