JDK8：HashMap源碼解析：hash方法

一、概述

我們知道在HashMap中，一個鍵值對存儲在HashMap内部資料的哪個位置上和K的hashCode值有關，這也是因為HashMap的hash算法要基于hashCode值來進行。

這裡要注意區分三個概念：hashCode值、hash值、hash方法、數組下标

hashCode值：是KV對中的K對象的hashCode方法的傳回值（若沒有重寫則預設用Object類的hashCode方法的生成值）

hash值：是在hashCode值的基礎上又進行了一步運算後的結果，這個運算過程就是hash方法。

數組下标：根據該hash值和數組長度計算出數組下标，計算公式：hash值 &（數組長度-1）= 下标。

我們要讨論的就是上面提到的hash方法，首先他是HashMap類中的一個靜态方法，該方法的代碼特别簡單，隻有兩行，文法很容易懂，可以其中具體用意确值得好好深入研究下。

我們首先讨論下數組下标計算過程，這個有助于我們了解hash方法的設計思想

二、數組下标計算

hash：hash值
length：數組長度
計算公式：hash  &（length-1）

若length=16，hash=1,那麼下标值計算過程如下：
    0000 0000 0000 0000 0000 0000 0000 1111    16-1 = 15，15對應的二進制值為1111
    0000 0000 0000 0000 0000 0000 0000 0001    1的二進制
    0000 0000 0000 0000 0000 0000 0000 0001    上兩行進行與運算，最終結果是1

若length=16，hash=17,那麼下标值計算過程如下：
    0000 0000 0000 0000 0000 0000 0000 1111    16-1 = 15，15對應的二進制值為1111
    0000 0000 0000 0000 0000 0000 0001 0001    17的二進制
    0000 0000 0000 0000 0000 0000 0000 0001    上兩行進行與運算，最終結果是1

若length=16，hash=33,那麼下标值計算過程如下：
    0000 0000 0000 0000 0000 0000 0000 1111    16-1 = 15，15對應的二進制值為1111
    0000 0000 0000 0000 0000 0000 0010 0001    33的二進制
    0000 0000 0000 0000 0000 0000 0000 0001    上兩行進行與運算，最終結果是1

若length=32，hash=1,那麼下标值計算過程如下：
    0000 0000 0000 0000 0000 0000 0001 1111    32-1 = 31，31對應的二進制值為11111
    0000 0000 0000 0000 0000 0000 0000 0001    1的二進制
    0000 0000 0000 0000 0000 0000 0000 0001    上兩行進行與運算，最終結果是1

若length=32，hash=17,那麼下标值計算過程如下：
    0000 0000 0000 0000 0000 0000 0001 1111    32-1 = 31，31對應的二進制值為11111
    0000 0000 0000 0000 0000 0000 0001 0001    17的二進制
    0000 0000 0000 0000 0000 0000 0001 0001    上兩行進行與運算，最終結果是17

若length=32，hash=33,那麼下标值計算過程如下：
    0000 0000 0000 0000 0000 0000 0001 1111    32-1 = 31，31對應的二進制值為11111
    0000 0000 0000 0000 0000 0000 0010 0001    33的二進制
    0000 0000 0000 0000 0000 0000 0000 0001    上兩行進行與運算，最終結果是1


(1,16)->1、(17,16)->1、(33,16)->1
(1,32)->1、(17,32)->17、(33,32)->1
總結：
hash  &（length-1）的運算效果等同于 hash%length。
我們知道hashMap的擴容規則是2倍擴容、數組長度一定是2的N次方。假設數組長度不是2的N次方，那麼再重複以上的計算過程，就達不到求模的效果了。

讨論完hashMap數組下标尋址過程後，我們可以得知

在put(K,V)的時候，會根據K的hash值和目前數組長度求模，得到該鍵值對應該存儲在數組的哪個位置。

在get(K)的時候，同樣會根據K的hash值和目前數組長度求模，定位到應該去數組的哪個位置尋找V。

按照上面舉得例子，put(K,V)，多個hash值和數組長度求模之後的結果相同時，大家都存儲在資料的同一位置，這種情況也叫hash碰撞，發生了這種碰撞時，大家會以先來後到的方式以連結清單的方式組織起來，那麼也就意味着我在get(K)的時候，雖然能夠定位到數組位置，還需要周遊連結清單，通過equals逐個對比之後才能确定需要傳回的V。

假設hash值都不相同，那麼hashMap數組的長度越大，碰撞的機率越小。

在數組長度為16時，當hash值為1、17、33時，大家都定位到下标1，那麼此時我們也可以這麼想一下，當我的hashMap數組的長度不變或者不會再變得時候，大于數組長度的hash值（17、33）對我hashMap來講和hash值1的效果是等同的。

在數組長度為65535時，當hash值為1、131071、262143時，大家都定位到下标1，那麼此時我們也可以這麼想一下，當我的hashMap數組的長度不變或者不會再變得時候，大于數組長度的hash值（131071、262143）對我hashMap來講和hash值1的效果是等同的。

以上兩種場景，如果假設：hash值 = hashCode值，就意味着無論是我們自己定義的hashCode還是預設的hashCode生成方式，大于數組長度的值并沒有産生我們想要達到的理想效果（我們希望，不同的hashCode能夠讓他分布到一個不會碰撞的位置），因為取模之後，他的位置可能至少會和某個小于數組長度的值碰撞。

什麼場景下可以避免碰撞：hashMap數組最大長度可知（要存儲的資料不超過數組最大長度），建立時就指定初始容量為最大長度，每個K的hash值各不同，且每個hash值都小于數組最大長度。這種場景有麼？有，但是我們大部分的應用場景都不會如此巧合或如此故意而為之。

再看下我們可能最常用的場景：

Map<String,Object> user = new HashMap<String,Object>(); // 預設内部資料長度為16
user.put("name", "kevin");
user.put("sex", 1);
user.put("level", 1);
user.put("phone", "13000000000");
user.put("address", "beijing fengtai");

以字元串作為key應該是比較常用的情況了，那麼這些K對應的hashCode是什麼呢？如果根據hashCode來定位下标的話又是什麼？

System.out.println("\"name\".hashCode()	: " +"name".hashCode());
System.out.println("\"sex\".hashCode()	: " +"sex".hashCode());
System.out.println("\"level\".hashCode()	: " +"level".hashCode());
System.out.println("\"phone\".hashCode()	: " +"phone".hashCode());
System.out.println("\"address\".hashCode()	: " +"address".hashCode());

System.out.println("--------*****---------");

System.out.println("\"name\".hashCode() & (16 - 1) 	:" + ("name".hashCode() & (16 - 1)));
System.out.println("\"sex\".hashCode() & (16 - 1) 	:" + ("sex".hashCode() & (16 - 1)));
System.out.println("\"level\".hashCode() & (16 - 1)	:" + ("level".hashCode() & (16 - 1)));
System.out.println("\"phone\".hashCode() & (16 - 1) 	:" + ("phone".hashCode() & (16 - 1)));
System.out.println("\"address\".hashCode() & (16 - 1) :" + ("address".hashCode() & (16 - 1)));

輸出結果：

"name".hashCode()	: 3373707
"sex".hashCode()	: 113766
"level".hashCode()	: 102865796
"phone".hashCode()	: 106642798
"address".hashCode()	: -1147692044
--------*****---------
"name".hashCode() & (16 - 1) 	:11
"sex".hashCode() & (16 - 1) 	:6
"level".hashCode() & (16 - 1)	:4
"phone".hashCode() & (16 - 1) 	:14
"address".hashCode() & (16 - 1) :4

如上輸出結果，我們向hashMap裡put了5個鍵值對，每個K的hashCode值均不相同，但是根據hashCode計算出來的下标卻存在碰撞（有兩個4），雖然hashCode的值很随機，但是限于我們數組長度，即便是很少的幾個資料，也是有很高機率碰撞的，這也就說明了這些看起來（絕對值）很大hashCode值和【0-15】範圍内的值對于長度為16的初始數組容量來講效果等同。

但是在資料量很少的情況下，即便發生了碰撞，性能上的劣勢也幾乎可以忽略不計。

但是我們上面的下标求值是一種假設，假設直接根據K的hashCode和數組長度求模，但是實際上是根據K的hash值和數組長度求模

那麼K的hash值是什麼，如何計算出來的呢，接下來就來讨論hash值的計算過程，hash方法。

三、hash方法解析

static final int hash(Object key) {
     int h;
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

1、如果key為空，那麼hash值置為0。HashMap允許null作為鍵，雖然這樣，因為null的hash值一定是0，而且null==null為真，是以HashMap裡面最多隻會有一個null鍵。而且這個null鍵一定是放在數組的第一個位置上。但是如果存在hash碰撞，該位置上形成連結清單了，那麼null鍵對應的節點就不确定在連結清單中的哪個位置了（取決于插入順序，并且每次擴容其在連結清單中的位置都可能會改變）。

2、如果key是個不為空的對象，那麼将key的hashCode值h和h無符号右移16位後的值做異或運算，得到最終的hash值。

從代碼中目前我們可确定的資訊是：hashCode值（h）是計算基礎，在h的基礎上進行了兩次位運算（無符号右移、異或）

我們還針對前面的user的key來重新進行一下測試

System.out.println("hash(\"name\")	: " + hash("name"));
System.out.println("hash(\"sex\")	: " + hash("sex"));
System.out.println("hash(\"level\")	: " + hash("level"));
System.out.println("hash(\"phone\")	: " + hash("phone"));
System.out.println("hash(\"address\")	: " + hash("address"));

System.out.println("--------*****---------");

System.out.println("hash(\"name\") & (16 - 1) 	:" + (hash("name") & (16 - 1)));
System.out.println("hash(\"sex\") & (16 - 1) 		:" + (hash("sex") & (16 - 1)));
System.out.println("hash(\"level\") & (16 - 1)	:" + (hash("level") & (16 - 1)));
System.out.println("hash(\"phone\") & (16 - 1) 	:" + (hash("phone") & (16 - 1)));
System.out.println("hash(\"address\") & (16 - 1) 	:" + (hash("address") & (16 - 1)));

輸出結果：

hash("name")	: 3373752
hash("sex")	: 113767
hash("level")	: 102866341
hash("phone")	: 106642229
hash("address")	: -1147723677
--------*****---------
hash("name") & (16 - 1) 	:8
hash("sex") & (16 - 1) 		:7
hash("level") & (16 - 1)	:5
hash("phone") & (16 - 1) 	:5
hash("address") & (16 - 1) 	:3

我們對比一下兩次的輸出結果

"name".hashCode()	    : 3373707               hash("name")	: 3373752
"sex".hashCode()	    : 113766                hash("sex")	        : 113767
"level".hashCode()	    : 102865796             hash("level")	: 102866341
"phone".hashCode()	    : 106642798             hash("phone")	: 106642229
"address".hashCode()	    : -1147692044           hash("address")	: -1147723677
--------*****---------
"name".hashCode() & (16 - 1) 	:11                 hash("name") & (16 - 1) 	:8
"sex".hashCode() & (16 - 1) 	:6                  hash("sex") & (16 - 1) 	:7
"level".hashCode() & (16 - 1)	:4                  hash("level") & (16 - 1)	:5
"phone".hashCode() & (16 - 1) 	:14                 hash("phone") & (16 - 1) 	:5
"address".hashCode() & (16 - 1) :4                  hash("address") & (16 - 1) 	:3

雖然經過hash算法之後與直接使用hashCode的輸出不同，但是數組下标還是出現了碰撞的情況（有兩個5）。是以hash方法也不能解決碰撞的問題（實際上碰撞不算是問題，我們隻是想盡可能的少發生）。那麼為什麼不直接用hashCode而非要經過這麼一種位運算來産生一個hash值呢。

我們先通過幾個例子來看下 h ^ (h >>> 16) 的計算過程

若h=17，那麼h ^ (h >>> 16)的計算可展現為如下過程：
    0000 0000 0000 0000 0000 0000 0001 0001    此時就是：h（17）的二進制。【高位是16個0】
    0000 0000 0000 0000 0000 0000 0000 0000    h（17）的二進制無符号右移16位後，此時就是：（h >>> 16）的二進制
    0000 0000 0000 0000 0000 0000 0001 0001    上兩行進行異或運算，此時就是：h ^ (h >>> 16)的二進制
最終可知（當h=17時）：h ^ (h >>> 16) = 17，并沒有發生變化。

若h=65535，那麼h ^ (h >>> 16)的計算可展現為如下過程：
    0000 0000 0000 0000 1111 1111 1111 1111    h【高位還是16個0】
    0000 0000 0000 0000 0000 0000 0000 0000    h >>> 16
    0000 0000 0000 0000 1111 1111 1111 1111    h ^ (h >>> 16)
最終可知（當h=65535時）：h ^ (h >>> 16) = 65535，并沒有發生變化。

若h=65536，那麼h ^ (h >>> 16)的計算可展現為如下過程：
    0000 0000 0000 0001 0000 0000 0000 0000     h【高位含有一個1】
    0000 0000 0000 0000 0000 0000 0000 0001     h >>> 16
    0000 0000 0000 0001 0000 0000 0000 0001     h ^ (h >>> 16)
最終可知（當h=65536時）：h ^ (h >>> 16) = 65537，hash後的值和原值不同。

若h=1147904，那麼h ^ (h >>> 16)的計算可展現為如下過程：
    0000 0000 0001 0001 1000 0100 0000 0000     h【高位含有兩個1，并不連續】
    0000 0000 0000 0000 0000 0000 0001 0001     h >>> 16
    0000 0000 0001 0001 1000 0100 0001 0001     h ^ (h >>> 16)
最終可知（當h=1147904時）：h ^ (h >>> 16) = 1147921，hash後的值和原值不同。

再來看個負數的情況，負數的情況稍微複雜些，主要因為負數的二進制和十進制之間的轉換會有【加|減|取反】等操作。
若h=-5，那麼h ^ (h >>> 16)的計算可展現為如下過程：
    0000 0000 0000 0000 0000 0000 0000 0101    先得到5的二進制
    1111 1111 1111 1111 1111 1111 1111 1010    5的二進制取反

    1111 1111 1111 1111 1111 1111 1111 1011    5的二進制取反後加1，此時就是：h（-5）的二進制。
    0000 0000 0000 0000 1111 1111 1111 1111    h（-5）的二進制無符号右移16位後，此時就是：（h >>> 16）的二進制
    1111 1111 1111 1111 0000 0000 0000 0100    上兩行進行異或運算，此時就是：h ^ (h >>> 16)的二進制
                                               接下來求一下這個二進制對應的10進制數值
    1111 1111 1111 1111 0000 0000 0000 0011    上一個二進制值減1
    0000 0000 0000 0000 1111 1111 1111 1100    再取反，此時十進制值為65532，但是需要加個負号
最終可知（當h=-5時）：h ^ (h >>> 16) = -65532，hash後的值和原值相差比較懸殊

1）上面的例子隻考慮了正數的情況，但可以得出以下結論

當h（hashCode值）在【0-65535】時，位運算後的結果仍然是h

當h（hashCode值）在【65535-N】時，位運算後的結果和h不同

當h（hashCode值）為負數時，位運算後的結果和h也不盡相同

2）我們上面user對象裡的key的hashCode值都沒有在【0-65535】範圍内，是以計算出來的結果與hashCode值存在差異。

為什麼【0-65535】範圍内的數值h，h ^ (h >>> 16) = h ？

從例子中的二進制的運算描述我們可以發現，【0-65535】範圍内的數值的二進制的高16位都是0，在進行無符号右移16位後，原來的高16位變成了現在的低16位，現在的高16位補了16個0，這種操作之後目前值就是32個0，以32個0去和任何整數值N做異或運算結果都還是N。而不再【0-65535】範圍内的數值的高16位都包含有1數字位，在無符号右移16位後，雖然高位仍然補了16個0，但是目前的低位任然包含有1數字位，是以最終的運算結果會發生變化。

而我們use對象裡的key的hashCode要麼大于65535、要麼小于0是以最終的hash值和hashCode都不相同，因為在異或運算中hashCode的高位中的非0數字位參與到了運算中。

四、hash方法的作用

前文通過執行個體已經印證了hash方法并不能杜絕碰撞。

"name".hashCode()	    : 3373707               hash("name")	: 3373752
"sex".hashCode()	    : 113766                hash("sex")	        : 113767
"level".hashCode()	    : 102865796             hash("level")	: 102866341
"phone".hashCode()	    : 106642798             hash("phone")	: 106642229

而且通過對比觀察，hash後的值和hashCode值雖然不盡相同，而對于正數的hashCode的産生的hash值即便和原值不同，差别也不是很大。為什麼不直接使用hashCode作為hash值呢？為什麼非要經過 h ^ (h >>> 16) 這一步運算呢？

在hash方法的注釋是這樣描述的：

/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower.  Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.)  So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/

大概意思就是：

尋址計算時，能夠參與到計算的有效二進制位僅僅是右側和數組長度值對應的那幾位，意味着發生碰撞的幾率會高。

通過移位和異或運算讓hashCode的高位能夠參與到尋址計算中。

采用這種方式是為了在性能、實用性、分布品質上取得一個平衡。

有很多hashCode算法都已經是分布合理的了，并且大量碰撞時，還可以通過樹結構來解決查詢性能問題。

是以用了性能比較高的位運算來讓高位參與到尋址運算中，位運算對于系統損耗相對低廉。

還提到了Float keys，個人認為說的應該是浮點數類型的對象作為key的時候，也順便測試了下

System.out.println("Float.valueOf(0.1f).hashCode()		:" + Float.valueOf(0.1f).hashCode());
System.out.println("Float.valueOf(1.3f).hashCode()		:" + Float.valueOf(1.3f).hashCode());
System.out.println("Float.valueOf(100.4f).hashCode()	:" + Float.valueOf(1.4f).hashCode());
System.out.println("Float.valueOf(987607.3f).hashCode()	:" + Float.valueOf(100000.3f).hashCode());
System.out.println("Float.valueOf(2809764.4f).hashCode()	:" + Float.valueOf(100000.4f).hashCode());
System.out.println("Float.valueOf(-100.3f).hashCode()	:" + Float.valueOf(-100.3f).hashCode());
System.out.println("Float.valueOf(-100.4f).hashCode()	:" + Float.valueOf(-100.4f).hashCode());

System.out.println("--------*****---------");

System.out.println("hash(0.1f)		:" + hash(0.1f));
System.out.println("hash(1.3f)		:" + hash(1.3f));
System.out.println("hash(1.4f)	:" + hash(1.4f));
System.out.println("hash(100000.3f)	:" + hash(100000.3f));
System.out.println("hash(100000.4f)	:" + hash(100000.4f));
System.out.println("hash(-100.3f)	:" + hash(-100.3f));
System.out.println("hash(-100.4f)	:" + hash(-100.4f));

輸出結果：

Float.valueOf(0.1f).hashCode()		:1036831949
Float.valueOf(1.3f).hashCode()		:1067869798
Float.valueOf(100.4f).hashCode()	:1068708659
Float.valueOf(987607.3f).hashCode()	:1203982374
Float.valueOf(2809764.4f).hashCode()	:1203982387
Float.valueOf(-100.3f).hashCode()	:-1027040870
Float.valueOf(-100.4f).hashCode()	:-1027027763
--------*****---------
hash(0.1f)	:1036841217
hash(1.3f)	:1067866560
hash(1.4f)	:1068698752
hash(100000.3f)	:1203967973
hash(100000.4f)	:1203967984
hash(-100.3f)	:-1027056814
hash(-100.4f)	:-1027076603

示例中的浮點數數值大小跨度還是比較大的，但是生成hashCode相差都不大，因為hashCode相差不大，是以最終的hash值相差也不大。那麼要怎麼證明hash之後就會減少碰撞呢？這個不太了解，看來還得看看大神們的分析。

JDK8：HashMap源碼解析：hash方法

繼續閱讀

Passing parameters to a Jasper report

java HashMap 與HashTable的差別

[轉]編寫高效的Android代碼

java增強for循環周遊Map集合問題

xmlbean 生成帶包路徑的jar

Java都有什麼進階技術？

重新認識HashMap

java寫發郵件（email.jar）的方法

HDU 1067（HASH + BFS）

WebService CXF學習（進階篇2）：複雜對象傳遞(List，Map)

Java1.8 對HashMap的resize()的了解

Java技術網站大全

Java中Integer和int的差別

LinkedHashMap的簡單用法

用JS/FLASH實作複制代碼到剪貼闆并且相容所有浏覽器

Mybatis下動态sql中##和$$差別