HashMap在jdk1.7和1.8中的實作

Java集合類的源碼是深入學習Java非常好的素材，源碼裡很多優雅的寫法和思路，會讓人歎為觀止。HashMap的源碼尤為經典，是非常值得去深入研究的，jdk1.8中HashMap發生了比較大的變化，這方面的東西也是各個公司高頻的考點。網上也有很多應對面試的标準答案，我之前也寫過類似的面試技巧（面試必備：Hashtable、HashMap、ConcurrentHashMap的原理與差別），應付一般的面試應該是夠了，但個人覺得這還是遠遠不夠，畢竟我們不能隻苟且于得到offer，更應去勇敢的追求詩和遠方（源碼）。

jdk版本目前更新的相對頻繁，好多小夥伴說jdk1.7才剛真正弄明白，1.8就出現了，1.8還用都沒開始用，更高的jdk版本就又釋出了。很多小夥伴大聲疾呼：臣妾真的學不動啦！這也許就是技術的最大魅力吧，活到老學到老，沒有人能說精通所有技術。不管jdk版本如何更新，目前jdk1.7和1.8還是各個公司的主力版本。不管是否學得動，難道各位小夥伴忘記了《倚天屠龍記》裡九陽真經裡的口訣：他強由他強，清風拂山崗；他橫由他橫，明月照大江。他自狠來他自惡，我自一口真氣足。（原諒我插入廣告緬懷金庸大師，年少時期讀的最多的書就是金庸大師的，遍布俠骨柔情大義啊）。這裡的“真氣”就是先掌握好jdk1.7和1.8，其它學不動的版本以後再說。

一、初窺HashMap

HashMap是應用更廣泛的哈希表實作，而且大部分情況下，都能在常數時間性能的情況下進行put和get操作。要掌握HashMap，主要從如下幾點來把握：

jdk1.7中底層是由數組（也有叫做“位桶”的）+連結清單實作；jdk1.8中底層是由數組+連結清單/紅黑樹實作

可以存儲null鍵和null值，線程不安全

初始size為16，擴容：newsize = oldsize*2，size一定為2的n次幂

擴容針對整個Map，每次擴容時，原來數組中的元素依次重新計算存放位置，并重新插入

插入元素後才判斷該不該擴容，有可能無效擴容（插入後如果擴容，如果沒有再次插入，就會産生無效擴容）

當Map中元素總數超過Entry數組的75%，觸發擴容操作，為了減少連結清單長度，元素配置設定更均勻

為什麼說HashMap是線程不安全的？在接近臨界點時，若此時兩個或者多個線程進行put操作，都會進行resize（擴容）和reHash（為key重新計算所在位置），而reHash在并發的情況下可能會形成連結清單環。

二、jdk1.7中HashMap的實作

HashMap底層維護的是數組+連結清單，我們可以通過一小段源碼來看看：

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

通過以上代碼可以看出初始容量（16）、負載因子以及對數組的說明。數組中的每一個元素其實就是Entry<K,V>[] table，Map中的key和value就是以Entry的形式存儲的。關于Entry<K,V>的具體定義參看如下源碼：

static class Entry<K,V> implements Map.Entry<K,V> {
 final K key;
 V value;
 Entry<K,V> next;
 int hash;
 
 Entry(int h, K k, V v, Entry<K,V> n) {
 value = v;
 next = n;
 key = k;
 hash = h;
 }
 
 public final K getKey() {
 return key;
 }
 
 public final V getValue() {
 return value;
 }
 
 public final V setValue(V newValue) {
 V oldValue = value;
 value = newValue;
 return oldValue;
 }
 
 public final boolean equals(Object o) {
 if (!(o instanceof Map.Entry))
 return false;
 Map.Entry e = (Map.Entry)o;
 Object k1 = getKey();
 Object k2 = e.getKey();
 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
 Object v1 = getValue();
 Object v2 = e.getValue();
 if (v1 == v2 || (v1 != null && v1.equals(v2)))
 return true;
 }
 return false;
 }
 
 public final int hashCode() {
 return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
 }
 
 public final String toString() {
 return getKey() + "=" + getValue();
 }
 
 /**
 * This method is invoked whenever the value in an entry is
 * overwritten by an invocation of put(k,v) for a key k that's already
 * in the HashMap.
 */
 void recordAccess(HashMap<K,V> m) {
 }
 
 /**
 * This method is invoked whenever the entry is
 * removed from the table.
 */
 void recordRemoval(HashMap<K,V> m) {
 }
}
           

當向 HashMap 中 put 一對鍵值時，它會根據 key的 hashCode 值計算出一個位置， 該位置就是此對象準備往數組中存放的位置。 該計算過程參看如下代碼：

transient int hashSeed = 0;
final int hash(Object k) {
 int h = hashSeed;
 if (0 != h && k instanceof String) {
 return sun.misc.Hashing.stringHash32((String) k);
 }
 
 h ^= k.hashCode();
 
 // This function ensures that hashCodes that differ only by
 // constant multiples at each bit position have a bounded
 // number of collisions (approximately 8 at default load factor).
 h ^= (h >>> 20) ^ (h >>> 12);
 return h ^ (h >>> 7) ^ (h >>> 4);
 }
 
 /**
 * Returns index for hash code h.
 */
 static int indexFor(int h, int length) {
 // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
 return h & (length-1);
 }
           

通過hash計算出來的值将會使用indexFor方法找到它應該所在的table下标。當兩個key通過hashCode計算相同時，則發生了hash沖突(碰撞)，HashMap解決hash沖突的方式是用連結清單。當發生hash沖突時，則将存放在數組中的Entry設定為新值的next（這裡要注意的是，比如A和B都hash後都映射到下标i中，之前已經有A了，當map.put(B)時，将B放到下标i中，A則為B的next，是以新值存放在數組中，舊值在新值的連結清單上）。即将新值作為此連結清單的頭節點，為什麼要這樣操作？據說後插入的Entry被查找的可能性更大（因為get查詢的時候會周遊整個連結清單），此處有待考究，如果有哪位大神知道，請留言告知。

如果該位置沒有對象存在，就将此對象直接放進數組當中；如果該位置已經有對象存在了，則順着此存在的對象的鍊開始尋找(為了判斷是否是否值相同，map不允許<key,value>鍵值對重複)， 如果此鍊上有對象的話，再去使用 equals方法進行比較，如果對此鍊上的每個對象的 equals 方法比較都為 false，則将該對象放到數組當中，然後将數組中該位置以前存在的那個對象連結到此對象的後面。

圖中，左邊部分即代表哈希表，也稱為哈希數組（預設數組大小是16，每對key-value鍵值對其實是存在map的内部類entry裡的），數組的每個元素都是一個單連結清單的頭節點，跟着的藍色連結清單是用來解決沖突的，如果不同的key映射到了數組的同一位置處，就将其放入單連結清單中。

前面說過HashMap的key是允許為null的，當出現這種情況時，會放到table[0]中。

private V putForNullKey(V value) {
 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
 if (e.key == null) {
 V oldValue = e.value;
 e.value = value;
 e.recordAccess(this);
 return oldValue;
 }
 }
 modCount++;
 addEntry(0, null, value, 0);
 return null;
}
           

當size>=threshold（ threshold等于“容量*負載因子”）時，會發生擴容。

id addEntry(int hash, K key, V value, int bucketIndex) {
 if ((size >= threshold) && (null != table[bucketIndex])) {
 resize(2 * table.length);
 hash = (null != key) ? hash(key) : 0;
 bucketIndex = indexFor(hash, table.length);
 }
 
 createEntry(hash, key, value, bucketIndex);
}
           

jdk1.7中resize，隻有當 size>=threshold并且 table中的那個槽中已經有Entry時，才會發生resize。即有可能雖然size>=threshold，但是必須等到每個槽都至少有一個Entry時，才會擴容,可以通過上面的代碼看到每次resize都會擴大一倍容量（2 * table.length）。

三、jdk1.8中HashMap的實作

在jdk1.8中HashMap的内部結構可以看作是數組(Node<K,V>[] table)和連結清單的複合結構，數組被分為一個個桶（bucket），通過哈希值決定了鍵值對在這個數組中的尋址（哈希值相同的鍵值對，則以連結清單形式存儲。有一點需要注意，如果連結清單大小超過門檻值（TREEIFY_THRESHOLD,8），圖中的連結清單就會被改造為樹形（紅黑樹）結構。

transient Node<K,V>[] table;

Entry的名字變成了Node，原因是和紅黑樹的實作TreeNode相關聯。

在分析jdk1.7中HashMap的hash沖突時，不知大家是否有個疑問就是萬一發生碰撞的節點非常多怎麼版？如果說成百上千個節點在hash時發生碰撞，存儲一個連結清單中，那麼如果要查找其中一個節點，那就不可避免的花費O(N)的查找時間，這将是多麼大的性能損失。這個問題終于在JDK1.8中得到了解決，在最壞的情況下，連結清單查找的時間複雜度為O(n),而紅黑樹一直是O(logn),這樣會提高HashMap的效率。

jdk1.7中HashMap采用的是位桶+連結清單的方式，即我們常說的散列連結清單的方式，而jdk1.8中采用的是位桶+連結清單/紅黑樹的方式，也是非線程安全的。當某個位桶的連結清單的長度達到某個閥值的時候，這個連結清單就将轉換成紅黑樹。

jdk1.8中，當同一個hash值的節點數不小于8時，将不再以單連結清單的形式存儲了，會被調整成一顆紅黑樹（上圖中null節點沒畫）。這就是jdk1.7與jdk1.8中HashMap實作的最大差別。

通過分析put方法的源碼，可以讓這種差別更直覺：

static final int TREEIFY_THRESHOLD = 8;
 
public V put(K key, V value) {
 return putVal(hash(key), key, value, false, true);
 }
 
 
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
 boolean evict) {
 Node<K,V>[] tab;
 Node<K,V> p;
 int n, i;
 //如果目前map中無資料，執行resize方法。并且傳回n
 if ((tab = table) == null || (n = tab.length) == 0)
 n = (tab = resize()).length;
 //如果要插入的鍵值對要存放的這個位置剛好沒有元素，那麼把他封裝成Node對象，放在這個位置上即可
 if ((p = tab[i = (n - 1) & hash]) == null)
 tab[i] = newNode(hash, key, value, null);
 //否則的話，說明這上面有元素
 else {
 Node<K,V> e; K k;
 //如果這個元素的key與要插入的一樣，那麼就替換一下。
 if (p.hash == hash &&
 ((k = p.key) == key || (key != null && key.equals(k))))
 e = p;
 //1.如果目前節點是TreeNode類型的資料，執行putTreeVal方法
 else if (p instanceof TreeNode)
 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
 else {
 //還是周遊這條鍊子上的資料，跟jdk7沒什麼差別
 for (int binCount = 0; ; ++binCount) {
 if ((e = p.next) == null) {
 p.next = newNode(hash, key, value, null);
 //2.完成了操作後多做了一件事情，判斷，并且可能執行treeifyBin方法
 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
 treeifyBin(tab, hash);
 break;
 }
 if (e.hash == hash &&
 ((k = e.key) == key || (key != null && key.equals(k))))
 break;
 p = e;
 }
 }
 if (e != null) { // existing mapping for key
 V oldValue = e.value;
 if (!onlyIfAbsent || oldValue == null) //true || --
 e.value = value;
 //3.
 afterNodeAccess(e);
 return oldValue;
 }
 }
 ++modCount;
 //判斷門檻值，決定是否擴容
 if (++size > threshold)
 resize();
 //4.
 afterNodeInsertion(evict);
 return null;
 }
           

以上代碼中的特别之處如下：

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
     treeifyBin(tab, hash);
           

treeifyBin()就是将連結清單轉換成紅黑樹。

putVal方法處理的邏輯比較多，包括初始化、擴容、樹化，近乎在這個方法中都能展現，針對源碼簡單講解下幾個關鍵點：

如果Node<K,V>[] table是null，resize方法會負責初始化，即如下代碼：

if ((tab = table) == null || (n = tab.length) == 0)
 n = (tab = resize()).length;
           

resize方法兼顧兩個職責，建立初始存儲表格，或者在容量不滿足需求的時候，進行擴容（resize）。

在放置新的鍵值對的過程中，如果發生下面條件，就會發生擴容。

if (++size > threshold)
 resize();
           

具體鍵值對在哈希表中的位置（數組index）取決于下面的位運算：

i = (n - 1) & hash
           

仔細觀察哈希值的源頭，會發現它并不是key本身的hashCode，而是來自于HashMap内部的另一個hash方法。為什麼這裡需要将高位資料移位到低位進行異或運算呢？這是因為有些資料計算出的哈希值差異主要在高位，而HashMap裡的哈希尋址是忽略容量以上的高位的，那麼這種處理就可以有效避免類似情況下的哈希碰撞。

在jdk1.8中取消了indefFor()方法，直接用(tab.length-1)&hash，是以看到這個，代表的就是數組的下角标。

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

為什麼HashMap為什麼要樹化？

之前在極客時間的專欄裡看到過一個解釋。本質上這是個安全問題。因為在元素放置過程中，如果一個對象哈希沖突，都被放置到同一個桶裡，則會形成一個連結清單，我們知道連結清單查詢是線性的，會嚴重影響存取的性能。而在現實世界，構造哈希沖突的資料并不是非常複雜的事情，惡意代碼就可以利用這些資料大量與伺服器端互動，導緻伺服器端CPU大量占用，這就構成了哈希碰撞拒絕服務攻擊，國内一線網際網路公司就發生過類似攻擊事件。

四、分析Hashtable、HashMap、TreeMap的差別

HashMap是繼承自AbstractMap類，而HashTable是繼承自Dictionary類。不過它們都實作了同時實作了map、Cloneable（可複制）、Serializable（可序列化）這三個接口。存儲的内容是基于key-value的鍵值對映射，不能由重複的key，而且一個key隻能映射一個value。

Hashtable的key、value都不能為null；HashMap的key、value可以為null，不過隻能有一個key為null，但可以有多個null的value；TreeMap鍵、值都不能為null。

Hashtable、HashMap具有無序特性。TreeMap是利用紅黑樹實作的（樹中的每個節點的值都會大于或等于它的左子樹中的所有節點的值，并且小于或等于它的右子樹中的所有節點的值），實作了SortMap接口，能夠對儲存的記錄根據鍵進行排序。是以一般需求排序的情況下首選TreeMap，預設按鍵的升序排序（深度優先搜尋），也可以自定義實作Comparator接口實作排序方式。

一般情況下我們選用HashMap，因為HashMap的鍵值對在取出時是随機的，其依據鍵的hashCode和鍵的equals方法存取資料，具有很快的通路速度，是以在Map中插入、删除及索引元素時其是效率最高的實作。而TreeMap的鍵值對在取出時是排過序的，是以效率會低點。

TreeMap是基于紅黑樹的一種提供順序通路的Map，與HashMap不同的是它的get、put、remove之類操作都是o(log(n))的時間複雜度，具體順序可以由指定的Comparator來決定，或者根據鍵的自然順序來判斷。

對HashMap做下總結：

HashMap基于哈希散清單實作 ，可以實作對資料的讀寫。将鍵值對傳遞給put方法時，它調用鍵對象的hashCode()方法來計算hashCode，然後找到相應的bucket位置（即數組）來儲存值對象。當擷取對象時，通過鍵對象的equals()方法找到正确的鍵值對，然後傳回值對象。HashMap使用連結清單來解決hash沖突問題，當發生沖突了，對象将會儲存在連結清單的頭節點中。HashMap在每個連結清單節點中儲存鍵值對對象，當兩個不同的鍵對象的hashCode相同時，它們會儲存在同一個bucket位置的連結清單中，如果連結清單大小超過門檻值（TREEIFY_THRESHOLD,8），連結清單就會被改造為樹形結構。

歡迎工作一到五年的Java工程師朋友們加入Java架構開發： 854393687

群内提供免費的Java架構學習資料（裡面有高可用、高并發、高性能及分布式、Jvm性能調優、Spring源碼，MyBatis，Netty,Redis,Kafka,Mysql,Zookeeper,Tomcat,Docker,Dubbo,Nginx等多個知識點的架構資料）合理利用自己每一分每一秒的時間來學習提升自己，不要再用"沒有時間“來掩飾自己思想上的懶惰！趁年輕，使勁拼，給未來的自己一個交代！