移步數(shù)據(jù)結(jié)構(gòu)--容器匯總（java & Android）
由于 HashMap 底層涉及到太多方面茸苇，一篇文章總是不能面面俱到盆驹，所以我們可以帶著面試官常問的幾個問題去看源碼

1. 了解底層如何存儲數(shù)據(jù)的
2. HashMap 的幾個主要方法
3. HashMap 是如何確定元素存儲位置的以及如何處理哈希沖突的
4. HashMap 擴(kuò)容機制是怎樣的
5. JDK 1.8 在擴(kuò)容和解決哈希沖突上對 HashMap 源碼做了哪些改動吉殃？有什么好處?

1 概述

為了方便下邊的敘述這里需要先對幾個常見的關(guān)于 HashMap 的知識點進(jìn)行下概述：

1. HashMap 存儲數(shù)據(jù)是根據(jù)鍵值對存儲數(shù)據(jù)的揩局，并且存儲多個數(shù)據(jù)時毙石，數(shù)據(jù)的鍵不能相同问裕，如果相同該鍵之前對應(yīng)的值將被覆蓋逮壁。注意如果想要保證 HashMap 能夠正確的存儲數(shù)據(jù)，請確保作為鍵的類粮宛，已經(jīng)正確覆寫了 equals() 方法貌踏。
2. HashMap 存儲數(shù)據(jù)的位置與添加數(shù)據(jù)的鍵的 hashCode() 返回值有關(guān)。所以在將元素使用 HashMap 存儲的時候請確保你已經(jīng)按照要求重寫了 hashCode(）方法窟勃。這里說有關(guān)系代表最終的存儲位置不一定就是 hashCode 的返回值祖乳。
3. HashMap 最多只允許一條存儲數(shù)據(jù)的鍵為 null，可允許多條數(shù)據(jù)的值為 null秉氧。
4. HashMap 存儲數(shù)據(jù)的順序是不確定的眷昆，并且可能會因為擴(kuò)容導(dǎo)致元素存儲位置改變。因此遍歷順序是不確定的汁咏。
5. HashMap 是線程不安全的亚斋，如果需要再多線程的情況下使用可以用 Collections.synchronizedMap(Map map) 方法使 HashMap 具有線程安全的能力，或者使用 ConcurrentHashMap攘滩。

2 HashMap 底層如何存儲數(shù)據(jù)的

2.1 JDK 1.7 之前的存儲結(jié)構(gòu)

即使 hashCode() 方法已經(jīng)寫得很完美了帅刊，終究還是有可能導(dǎo)致 「hash碰撞」的，HashMap 作為使用 hash 值來決定元素存儲位置的集合也是需要處理 hash 沖突的漂问。在1.7之前JDK采用「拉鏈法」來存儲數(shù)據(jù)赖瞒，即數(shù)組和鏈表結(jié)合的方式：

image

• 「拉鏈法」用專業(yè)點的名詞來說叫做鏈地址法女揭。簡單來說，就是數(shù)組加鏈表的結(jié)合栏饮。在每個數(shù)組元素上存儲的都是一個鏈表吧兔。
• 我們之前說到不同的 key 可能經(jīng)過 hash 運算可能會得到相同的地址，但是一個數(shù)組單位上只能存放一個元素袍嬉，采用鏈地址法以后境蔼，如果遇到相同的 hash 值的 key 的時候，我們可以將它放到作為數(shù)組元素的鏈表上伺通。待我們?nèi)ト≡氐臅r候通過 hash 運算的結(jié)果找到這個鏈表箍土，再在鏈表中找到與 key 相同的節(jié)點，就能找到 key 相應(yīng)的值了罐监。
• JDK1.7中新添加進(jìn)來的元素總是放在數(shù)組相應(yīng)的角標(biāo)位置涮帘，而原來處于該角標(biāo)的位置的節(jié)點作為 next 節(jié)點放到新節(jié)點的后邊。

2.2 JDK1.8中的存儲結(jié)構(gòu)笑诅。

• 對于 JDK1.8 之后的HashMap底層在解決哈希沖突的時候调缨，就不單單是使用數(shù)組加上單鏈表的組合了，因為當(dāng)處理如果 hash 值沖突較多的情況下吆你，鏈表的長度就會越來越長弦叶，此時通過單鏈表來尋找對應(yīng) Key 對應(yīng)的 Value 的時候就會使得時間復(fù)雜度達(dá)到 O(n),
• 因此在 JDK1.8 之后，在鏈表新增節(jié)點導(dǎo)致鏈表長度超過 TREEIFY_THRESHOLD = 8 的時候妇多，就會在添加元素的同時將原來的單鏈表轉(zhuǎn)化為紅黑樹伤哺。

• 對數(shù)據(jù)結(jié)構(gòu)很在行的讀者應(yīng)該，知道紅黑樹是一種易于增刪改查的二叉樹者祖，他對與數(shù)據(jù)的查詢的時間復(fù)雜度是 O(logn) 級別立莉，所以利用紅黑樹的特點就可以更高效的對 HashMap 中的元素進(jìn)行操作。

  
  
  image
• JDK1.8 對于HashMap 底層存儲結(jié)構(gòu)優(yōu)化在于：當(dāng)鏈表新增節(jié)點導(dǎo)致鏈表長度超過8的時候七问，就會將原有的鏈表轉(zhuǎn)為紅黑樹來存儲數(shù)據(jù)蜓耻。

3 關(guān)于 HashMap 源碼中提到的幾個重要概念

關(guān)于 HashMap 源碼中分析的文章一般都會提及幾個重要的概念：

3.1 重要參數(shù)

1. 哈希桶（buckets）：在 HashMap 的注釋里使用哈希桶來形象的表示數(shù)組中每個地址位置。注意這里并不是數(shù)組本身械巡，數(shù)組是裝哈希桶的刹淌，他可以被稱為哈希表。
2. 初始容量(initial capacity) : 這個很容易理解讥耗，就是哈希表中哈希桶初始的數(shù)量。如果我們沒有通過構(gòu)造方法修改這個容量值默認(rèn)為DEFAULT_INITIAL_CAPACITY = 1<<4 即16古程。值得注意的是為了保證 HashMap 添加和查找的高效性挣磨，HashMap 的容量總是 2^n 的形式雇逞。
3. 加載因子(load factor)：加載因子是哈希表（散列表）在其容量自動增加之前被允許獲得的最大數(shù)量的度量。當(dāng)哈希表中的條目數(shù)量超過負(fù)載因子和當(dāng)前容量的乘積時，散列表就會被重新映射（即重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)）呜达，重新創(chuàng)建的散列表容量大約是之前散列表哈系統(tǒng)桶數(shù)量的兩倍谣蠢。默認(rèn)加載因子（0.75）在時間和空間成本之間提供了良好的折衷眉踱。加載因子過大會導(dǎo)致很容易鏈表過長谈喳，加載因子很小又容易導(dǎo)致頻繁的擴(kuò)容戈泼。所以不要輕易試著去改變這個默認(rèn)值大猛。
4. 擴(kuò)容閾值（threshold）：其實在說加載因子的時候已經(jīng)提到了擴(kuò)容閾值了挽绩，擴(kuò)容閾值 = 哈希表容量 * 加載因子唉堪。哈希表的鍵值對總數(shù) = 所有哈希桶中所有鏈表節(jié)點數(shù)的加和唠亚，擴(kuò)容閾值比較的是是鍵值對的個數(shù)而不是哈希表的數(shù)組中有多少個位置被占了灶搜。
5. 樹化閥值(TREEIFY_THRESHOLD) ：這個參數(shù)概念是在 JDK1.8后加入的占调，它的含義代表一個哈希桶中的節(jié)點個數(shù)大于該值（默認(rèn)為8）的時候?qū)晦D(zhuǎn)為紅黑樹行存儲結(jié)構(gòu)究珊。
6. 非樹化閥值(UNTREEIFY_THRESHOLD)： 與樹化閾值相對應(yīng)剿涮，表示當(dāng)一個已經(jīng)轉(zhuǎn)化為數(shù)形存儲結(jié)構(gòu)的哈希桶中節(jié)點數(shù)量小于該值（默認(rèn)為 6）的時候?qū)⒃俅胃臑閱捂湵淼母袷酱鎯Α?dǎo)致這種操作的原因可能有刪除節(jié)點或者擴(kuò)容怀吻。
7. 最小樹化容量(MIN_TREEIFY_CAPACITY): 經(jīng)過上邊的介紹我們只知道，當(dāng)鏈表的節(jié)點數(shù)超過8的時候就會轉(zhuǎn)化為樹化存儲屑咳，其實對于轉(zhuǎn)化還有一個要求就是哈希表的數(shù)量超過最小樹化容量的要求（默認(rèn)要求是 64）,且為了避免進(jìn)行擴(kuò)容兆龙、樹形化選擇的沖突紫皇，這個值不能小于 4 * TREEIFY_THRESHOLD);在達(dá)到該有求之前優(yōu)先選擇擴(kuò)容坝橡。擴(kuò)容因為因為容量的變化可能會使單鏈表的長度改變计寇。

與這個幾個概念對應(yīng)的在 HashMap 中幾個常亮量番宁，由于上邊的介紹比較詳細(xì)了蝶押，下邊僅列出幾個變量的聲明：

/*默認(rèn)初始容量*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/*最大存儲容量*/
static final int MAXIMUM_CAPACITY = 1 << 30;

/*默認(rèn)加載因子*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/*默認(rèn)樹化閾值*/
static final int TREEIFY_THRESHOLD = 8;

/*默認(rèn)非樹化閾值*/
static final int UNTREEIFY_THRESHOLD = 6;

/*默認(rèn)最小樹化容量*/
static final int MIN_TREEIFY_CAPACITY = 64;

對應(yīng)的還有幾個全局變量：

// 擴(kuò)容閾值 = 容量 x 加載因子
int threshold;

//存儲哈希桶的數(shù)組，哈希桶中裝的是一個單鏈表或一顆紅黑樹赶盔，長度一定是 2^n
transient Node<K,V>[] table;  
  
// HashMap中存儲的鍵值對的數(shù)量注意這里是鍵值對的個數(shù)而不是數(shù)組的長度
transient int size;
  
//所有鍵值對的Set集合 區(qū)分于 table 可以調(diào)用 entrySet(）得到該集合
transient Set<Map.Entry<K,V>> entrySet;
  
//操作數(shù)記錄 為了多線程操作時 Fast-fail 機制
transient int modCount;

3.2 基本存儲單元

• HashMap 在 JDK 1.7 中只有 Entry 一種存儲單元
• 在 JDK1.8 中由于有了紅黑樹的存在于未，就多了一種存儲單元烘浦，而 Entry 也隨之應(yīng)景的改為名為 Node闷叉。我們先來看下單鏈表節(jié)點的表示方法 ：

/**
 * 內(nèi)部類 Node 實現(xiàn)基類的內(nèi)部接口 Map.Entry<K,V>
 * 
 */
static class Node<K,V> implements Map.Entry<K,V> {
   //此值是在數(shù)組索引位置
   final int hash;
   //節(jié)點的鍵
   final K key;
   //節(jié)點的值
   V value;
   //單鏈表中下一個節(jié)點
   Node<K,V> next;
    
   Node(int hash, K key, V value, Node<K,V> next) {
       this.hash = hash;
       this.key = key;
       this.value = value;
       this.next = next;
   }

   public final K getKey()        { return key; }
   public final V getValue()      { return value; }
   public final String toString() { return key + "=" + value; }
    //節(jié)點的 hashCode 值通過 key 的哈希值和 value 的哈希值異或得到蚯瞧，沒發(fā)現(xiàn)在源碼中中有用到状知。
   public final int hashCode() {
       return Objects.hashCode(key) ^ Objects.hashCode(value);
   }

   //更新相同 key 對應(yīng)的 Value 值
   public final V setValue(V newValue) {
       V oldValue = value;
       value = newValue;
       return oldValue;
   }
 //equals 方法，鍵值同時相同才節(jié)點才相同
   public final boolean equals(Object o) {
       if (o == this)
           return true;
       if (o instanceof Map.Entry) {
           Map.Entry<?,?> e = (Map.Entry<?,?>)o;
           if (Objects.equals(key, e.getKey()) &&
               Objects.equals(value, e.getValue()))
               return true;
       }
       return false;
   }
}

對于JDK1.8 新增的紅黑樹節(jié)點，這里不做展開敘述答朋，有興趣的朋友可以查看 HashMap 在 JDK 1.8 后新增的紅黑樹結(jié)構(gòu)這篇文章來了解一下 JDK1.8對于紅黑樹的操作梦碗。

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
   TreeNode<K,V> parent;  // red-black tree links
   TreeNode<K,V> left;
   TreeNode<K,V> right;
   TreeNode<K,V> prev;    // needed to unlink next upon deletion
   boolean red;
   TreeNode(int hash, K key, V val, Node<K,V> next) {
       super(hash, key, val, next);
   }
   ·········
}

4 HashMap 構(gòu)造方法

HashMap 構(gòu)造方法一共有三個：

4.1 HashMap(int initialCapacity, float loadFactor)

• 可以指定期望初始容量和加載因子的構(gòu)造函數(shù)，有了這兩個值斩例，我們就可以算出上邊說到的 threshold 加載因子念赶。其中加載因子不可以小于0叉谜，并沒有規(guī)定不可以大于 1正罢，但是不能等于無窮.

大家可能疑惑 Float.isNaN() 其實 NaN 就是 not a number 的縮寫翻具，我們知道在運算 1/0 的時候回拋出異常裆泳，但是如果我們的除數(shù)指定為浮點數(shù) 1/0.0f 的時候就不會拋出異常了运提。計算器運算出的結(jié)果可以當(dāng)做一個極值也就是無窮大民泵，無窮大不是個數(shù)所以 1/0.0f 返回結(jié)果是 Infinity 無窮,使用 Float.isNaN(）判斷將會返回 true栈妆。

 public HashMap(int initialCapacity, float loadFactor) {
    // 指定期望初始容量小于0將會拋出非法參數(shù)異常
   if (initialCapacity < 0)
       throw new IllegalArgumentException("Illegal initial capacity: " +
                                          initialCapacity);
   // 期望初始容量不可以大于最大值 2^30  實際上我們也不會用到這么大的容量                                      
   if (initialCapacity > MAXIMUM_CAPACITY)
       initialCapacity = MAXIMUM_CAPACITY;
  // 加載因子必須大于0 不能為無窮大   
   if (loadFactor <= 0 || Float.isNaN(loadFactor))
       throw new IllegalArgumentException("Illegal load factor: " +
                                          loadFactor);
   this.loadFactor = loadFactor;//初始化全局加載因子變量
   this.threshold = tableSizeFor(initialCapacity);//根據(jù)初始容量計算計算擴(kuò)容閾值
}

咦？不是說好擴(kuò)容閾值 = 哈希表容量 * 加載因子么寥假？為什么還要用到下邊這個方法呢糕韧？我們之前說了參數(shù) initialCapacity 只是期望容量萤彩，不知道大家發(fā)現(xiàn)沒我們**這個構(gòu)造函數(shù)并沒有初始化 Node<K,V>[] table **，事實上真正指定哈希表容量總是在第一次添加元素的時候怕吴，這點和 ArrayList 的機制有所不同转绷。等我們說到擴(kuò)容機制的時候我們就可以看到相關(guān)代碼了议经。

//根據(jù)期望容量返回一個 >= cap 的擴(kuò)容閾值煞肾，并且這個閾值一定是 2^n 
static final int tableSizeFor(int cap) {
   int n = cap - 1;
   n |= n >>> 1;
   n |= n >>> 2;
   n |= n >>> 4;
   n |= n >>> 8;
   n |= n >>> 16;
   //經(jīng)過上述面的 或和位移 運算习绢， n 最終各位都是1 
   //最終結(jié)果 +1 也就保證了返回的肯定是 2^n 
   return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

4.2 只指定初始容量的構(gòu)造函數(shù)

這個就比較簡單了闪萄，將指定的期望初容量和默認(rèn)加載因子傳遞給兩個參數(shù)構(gòu)造方法败去。這里就不在贅述。

public HashMap(int initialCapacity) {
   this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

4.3 無參數(shù)構(gòu)造函數(shù)

這也是我們最常用的一個構(gòu)造函數(shù)葫辐，該方法初始化了加載因子為默認(rèn)值，并沒有調(diào)動其他的構(gòu)造方法焊傅，跟我們之前說的一樣，哈希表的大小以及其他參數(shù)都會在第一調(diào)用擴(kuò)容函數(shù)的初始化為默認(rèn)值握巢。

public HashMap() {
   this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

4.4 傳入一個 Map 集合的構(gòu)造參數(shù)

該方法解釋起來就比較麻煩了暴浦，因為他在初始化的時候就涉及了添加元素歌焦，擴(kuò)容這兩大重要的方法。這里先把它掛起來纷铣，緊接著我們講完了擴(kuò)容機制再回來看就好了搜立。

public HashMap(Map<? extends K, ? extends V> m) {
   this.loadFactor = DEFAULT_LOAD_FACTOR;
   putMapEntries(m, false);
}

5 HashMap 如何確定添加元素的位置

• 在分析 HashMap 添加元素的方法之前儒拂，我們需要先來了解下见转，如何確定元素在 HashMap 中的位置的斩箫。
• 我們知道 HashMap 底層是哈希表乘客，哈希表依靠 hash 值去確定元素存儲位置。HashMap 在 JDK 1.7 和 JDK1.8中采用的 hash 方法并不是完全相同牡直。

5.1 JDK 1.7 中 hash 方法的實現(xiàn)：

這里提出一個概念擾動函數(shù)碰逸，我們知道Map 文中存放鍵值對的位置由鍵的 hash 值決定，但是鍵的 hashCode 函數(shù)返回值不一定滿足胳喷，哈希表長度的要求厌蔽，所以在存儲元素之前需要對 key 的 hash 值進(jìn)行一步擾動處理纬向。

//4次位運算 + 5次異或運算 
//這種算法可以防止低位不變逾条，高位變化時师脂，造成的 hash 沖突
static final int hash(Object k) {
   int h = 0;
   h ^= k.hashCode(); 
   h ^= (h >>> 20) ^ (h >>> 12);
   return h ^ (h >>> 7) ^ (h >>> 4);
}

4.2 JDK1.8 中 hash 函數(shù)的實現(xiàn)

• JDK1.8中再次優(yōu)化了這個哈希函數(shù)，把 key 的 hashCode 方法返回值右移16位酌心，即丟棄低16位，高16位全為0 侯勉，然后在于 hashCode 返回值做異或運算址貌，即高 16 位與低 16 位進(jìn)行異或運算芳誓，這么做可以在數(shù)組 table 的 length 比較小的時候匿值，也能保證考慮到高低Bit都參與到 hash 的計算中挟憔，同時不會有太大的開銷政恍，擾動處理次數(shù)也從 4次位運算 + 5次異或運算 降低到 1次位運算 + 1次異或運算

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

4.3 indexFor(int h, int length)數(shù)組中的角標(biāo)

進(jìn)過上述的擾動函數(shù)只是得到了合適的 hash 值篙耗，但是還沒有確定在 Node[] 數(shù)組中的角標(biāo)脯燃，在 JDK1.7中存在一個函數(shù)辕棚，JDK1.8中雖然沒有但是只是把這步運算放到了 put 函數(shù)中。我們就看下這個函數(shù)實現(xiàn)：

static int indexFor(int h, int length) {
     return h & (length-1);  // 取模運算
}

• 為了讓 hash 值能夠?qū)?yīng)到現(xiàn)有數(shù)組中的位置懈糯，即 hash % length赚哗，得到結(jié)果作為角標(biāo)位置。但是 HashMap 就厲害了够掠，連這一步取模運算的都優(yōu)化了。我們需要知道一個計算機對于2進(jìn)制的運算是要快于10進(jìn)制的竖哩，取模算是10進(jìn)制的運算了相叁，而位與運算就要更高效一些了。
• 我們知道 HashMap 底層數(shù)組的長度總是 2^n ,轉(zhuǎn)為二進(jìn)制總是 1000 即1后邊多個0的情況虑润。此時一個數(shù)與 2^n 取模梁剔，等價于 一個數(shù)與 2^n - 1做位與運算荣病。而 JDK 中就使用h & (length-1) 運算替代了對 length取模。

image

4.4 小結(jié)

• 在存儲元素之前，HashMap 會對 key 的 hashCode 返回值做進(jìn)一步擾動函數(shù)處理终惑，1.7 中擾動函數(shù)使用了 4次位運算 + 5次異或運算，1.8 中降低到 1次位運算 + 1次異或運算
• 擾動處理后的 hash 與 哈希表數(shù)組length -1 做位與運算得到最終元素儲存的哈希桶角標(biāo)位置霸奕。

5 HashMap 的添加元素

5.1 put(K key, V value) 函數(shù)

• 對于理解 HashMap 源碼一方面要了解存儲的數(shù)據(jù)結(jié)構(gòu)，另一方面也要了解具體是如何添加元素的煤惩。
• 下面我們就來看下 put(K key, V value) 函數(shù)。

// 可以看到具體的添加行為在 putVal 方法中進(jìn)行
public V put(K key, V value) {
   return putVal(hash(key), key, value, false, true);
}

5.2 putVal

對于 putVal 前三個參數(shù)很好理解什猖，第4個參數(shù) onlyIfAbsent 表示只有當(dāng)對應(yīng) key 的位置為空的時候替換元素降铸，一般傳 false推掸，在 JDK1.8中新增方法 public V putIfAbsent(K key, V value) 傳 true登渣，第 5 個參數(shù) evict 如果是 false粘优。那么表示是在初始化時調(diào)用的:

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
              boolean evict) {
              
   Node<K,V>[] tab; Node<K,V> p; int n, i;
   //如果是第一添加元素 table = null 則需要擴(kuò)容
   if ((tab = table) == null || (n = tab.length) == 0)
       n = (tab = resize()).length;// n 表示擴(kuò)容后數(shù)組的長度
   //  i = (n - 1) & hash 即上邊講得元素存儲在 map 中的數(shù)組角標(biāo)計算
   // 如果對應(yīng)數(shù)組沒有元素沒發(fā)生 hash 碰撞 則直接賦值給數(shù)組中 index 位置   
   if ((p = tab[i = (n - 1) & hash]) == null)
       tab[i] = newNode(hash, key, value, null);
   else {// 發(fā)生 hash 碰撞了
       Node<K,V> e; K k;
        //如果對應(yīng)位置有已經(jīng)有元素了 且 key 是相同的則覆蓋元素
       if (p.hash == hash &&
           ((k = p.key) == key || (key != null && key.equals(k))))
           e = p;
       else if (p instanceof TreeNode)//如果添加當(dāng)前節(jié)點已經(jīng)為紅黑樹呻顽，則需要轉(zhuǎn)為紅黑樹中的節(jié)點
           e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
       else {// hash 值計算出的數(shù)組索引相同雹顺，但 key 并不同的時候，        // 循環(huán)整個單鏈表
           for (int binCount = 0; ; ++binCount) {
               if ((e = p.next) == null) {//遍歷到尾部
                    // 創(chuàng)建新的節(jié)點廊遍，拼接到鏈表尾部
                   p.next = newNode(hash, key, value, null);             // 如果添加后 bitCount 大于等于樹化閾值后進(jìn)行哈希桶樹化操作
                   if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                       treeifyBin(tab, hash);
                   break;
               }
               //如果遍歷過程中找到鏈表中有個節(jié)點的 key 與 當(dāng)前要插入元素的 key 相同嬉愧，此時 e 所指的節(jié)點為需要替換 Value 的節(jié)點，并結(jié)束循環(huán)
               if (e.hash == hash &&
                   ((k = e.key) == key || (key != null && key.equals(k))))
                   break;
               //移動指針    
               p = e;
           }
       }
       //如果循環(huán)完后 e!=null 代表需要替換e所指節(jié)點 Value
       if (e != null) { // existing mapping for key
           V oldValue = e.value//保存原來的 Value 作為返回值
           // onlyIfAbsent 一般為 false 所以替換原來的 Value
           if (!onlyIfAbsent || oldValue == null)
               e.value = value;
            //這個方法在 HashMap 中是空實現(xiàn)没酣，在 LinkedHashMap 中有關(guān)系   
           afterNodeAccess(e);
           return oldValue;
       }
   }
   //操作數(shù)增加
   ++modCount;
   //如果 size 大于擴(kuò)容閾值則表示需要擴(kuò)容
   if (++size > threshold)
       resize();
   afterNodeInsertion(evict);
   return null;
}

由于添加元素中設(shè)計邏輯有點復(fù)雜，這里引用一張圖來說明卵迂，理解

image

5.3 添加元素過程：

1. 如果 Node[] table 表為 null ,則表示是第一次添加元素四康，講構(gòu)造函數(shù)也提到了，及時構(gòu)造函數(shù)指定了期望初始容量狭握，在第一次添加元素的時候也為空闪金。這時候需要進(jìn)行首次擴(kuò)容過程。
2. 計算對應(yīng)的鍵值對在 table 表中的索引位置论颅，通過i = (n - 1) & hash 獲得哎垦。
3. 判斷索引位置是否有元素如果沒有元素則直接插入到數(shù)組中。如果有元素且key 相同恃疯，則覆蓋 value 值漏设，這里判斷是用的 equals 這就表示要正確的存儲元素，就必須按照業(yè)務(wù)要求覆寫 key 的 equals 方法
4. 如果索引位置的 key 不相同今妄，則需要遍歷單鏈表郑口，如果遍歷過如果有與 key 相同的節(jié)點，則保存索引盾鳞，替換 Value犬性；如果沒有相同節(jié)點，則在但單鏈表尾部插入新節(jié)點腾仅。這里操作與1.7不同乒裆，1.7新來的節(jié)點總是在數(shù)組索引位置，而之前的元素作為下個節(jié)點拼接到新節(jié)點尾部推励。
5. 如果插入節(jié)點后鏈表的長度大于樹化閾值鹤耍，則需要將單鏈表轉(zhuǎn)為紅黑樹肉迫。
6. 成功插入節(jié)點后，判斷鍵值對個數(shù)是否大于擴(kuò)容閾值稿黄，如果大于了則需要再次擴(kuò)容喊衫。至此整個插入元素過程結(jié)束。

6 HashMap 的擴(kuò)容過程

• 在上邊說明 HashMap 的 putVal 方法時候杆怕，多次提到了擴(kuò)容函數(shù)族购，擴(kuò)容函數(shù)也是我們理解 HashMap 源碼的重中之重。

final Node<K,V>[] resize() {
   // oldTab 指向舊的 table 表
   Node<K,V>[] oldTab = table;
   // oldCap 代表擴(kuò)容前 table 表的數(shù)組長度财著，oldTab 第一次添加元素的時候為 null 
   int oldCap = (oldTab == null) ? 0 : oldTab.length;
   // 舊的擴(kuò)容閾值
   int oldThr = threshold;
   // 初始化新的閾值和容量
   int newCap, newThr = 0;
   // 如果 oldCap > 0 則會將新容量擴(kuò)大到原來的2倍联四，擴(kuò)容閾值也將擴(kuò)大到原來閾值的兩倍
   if (oldCap > 0) {
       // 如果舊的容量已經(jīng)達(dá)到最大容量 2^30 那么就不在繼續(xù)擴(kuò)容直接返回，將擴(kuò)容閾值設(shè)置到 Integer.MAX_VALUE撑教，并不代表不能裝新元素朝墩，只是數(shù)組長度將不會變化
       if (oldCap >= MAXIMUM_CAPACITY) {
           threshold = Integer.MAX_VALUE;
           return oldTab;
       }//新容量擴(kuò)大到原來的2倍，擴(kuò)容閾值也將擴(kuò)大到原來閾值的兩倍
       else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
           newThr = oldThr << 1; // double threshold
   }
   //oldThr 不為空伟姐，代表我們使用帶參數(shù)的構(gòu)造方法指定了加載因子并計算了
   //初始初始閾值 會將擴(kuò)容閾值 賦值給初始容量這里不再是期望容量收苏，
   //但是 >= 指定的期望容量
   else if (oldThr > 0) // initial capacity was placed in threshold
       newCap = oldThr;
   else {
        // 空參數(shù)構(gòu)造會走這里初始化容量，和擴(kuò)容閾值 分別是 16 和 12
       newCap = DEFAULT_INITIAL_CAPACITY;
       newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
   }
   //如果新的擴(kuò)容閾值是0愤兵，對應(yīng)的是當(dāng)前 table 為空鹿霸，但是有閾值的情況
   if (newThr == 0) {
        //計算新的擴(kuò)容閾值
       float ft = (float)newCap * loadFactor;
       // 如果新的容量不大于 2^30 且 ft 不大于 2^30 的時候賦值給 newThr 
       //否則 使用 Integer.MAX_VALUE
       newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                 (int)ft : Integer.MAX_VALUE);
   }
   //更新全局?jǐn)U容閾值
   threshold = newThr;
   @SuppressWarnings({"rawtypes","unchecked"})
    //使用新的容量創(chuàng)建新的哈希表的數(shù)組
   Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
   table = newTab;
   //如果老的數(shù)組不為空將進(jìn)行重新插入操作否則直接返回
   if (oldTab != null) {
        //遍歷老數(shù)組中每個位置的鏈表或者紅黑樹重新計算節(jié)點位置，插入新數(shù)組
       for (int j = 0; j < oldCap; ++j) {
           Node<K,V> e;//用來存儲對應(yīng)數(shù)組位置鏈表頭節(jié)點
           //如果當(dāng)前數(shù)組位置存在元素
           if ((e = oldTab[j]) != null) {
                // 釋放原來數(shù)組中的對應(yīng)的空間
               oldTab[j] = null;
               // 如果鏈表只有一個節(jié)點秆乳，
               //則使用新的數(shù)組長度計算節(jié)點位于新數(shù)組中的角標(biāo)并插入
               if (e.next == null)
                   newTab[e.hash & (newCap - 1)] = e;
               else if (e instanceof TreeNode)//如果當(dāng)前節(jié)點為紅黑樹則需要進(jìn)一步確定樹中節(jié)點位于新數(shù)組中的位置懦鼠。
                   ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
               else { // preserve order
                   //因為擴(kuò)容是容量翻倍，
                   //原鏈表上的每個節(jié)點 現(xiàn)在可能存放在原來的下標(biāo)屹堰，即low位肛冶，
                   //或者擴(kuò)容后的下標(biāo)，即high位
              //低位鏈表的頭結(jié)點扯键、尾節(jié)點
              Node<K,V> loHead = null, loTail = null;
              //高位鏈表的頭節(jié)點睦袖、尾節(jié)點
              Node<K,V> hiHead = null, hiTail = null;
              Node<K,V> next;//用來存放原鏈表中的節(jié)點
              do {
                  next = e.next;
                  // 利用哈希值 & 舊的容量，可以得到哈希值去模后荣刑，
                  //是大于等于 oldCap 還是小于 oldCap馅笙，
                  //等于 0 代表小于 oldCap，應(yīng)該存放在低位厉亏，
                  //否則存放在高位（稍后有圖片說明）
                  if ((e.hash & oldCap) == 0) {
                      //給頭尾節(jié)點指針賦值
                      if (loTail == null)
                          loHead = e;
                      else
                          loTail.next = e;
                      loTail = e;
                  }//高位也是相同的邏輯
                  else {
                      if (hiTail == null)
                          hiHead = e;
                      else
                          hiTail.next = e;
                      hiTail = e;
                  }//循環(huán)直到鏈表結(jié)束
              } while ((e = next) != null);
              //將低位鏈表存放在原index處董习，
              if (loTail != null) {
                  loTail.next = null;
                  newTab[j] = loHead;
              }
              //將高位鏈表存放在新index處
              if (hiTail != null) {
                  hiTail.next = null;
                  newTab[j + oldCap] = hiHead;
              }
           }
       }
   }
   return newTab;
}

相信大家看到擴(kuò)容的整個函數(shù)后對擴(kuò)容機制應(yīng)該有所了解了，整體分為兩部分：

• 1. 尋找擴(kuò)容后數(shù)組的大小以及新的擴(kuò)容閾值
• 2. 將原有哈希表拷貝到新的哈希表中叶堆。

第一部分沒的說阱飘，但是第二部分我看的有點懵逼了

• JDK 1.8 不像 JDK1.7中會重新計算每個節(jié)點在新哈希表中的位置，而是通過 (e.hash & oldCap) == 0是否等于0 就可以得出原來鏈表中的節(jié)點在新哈希表的位置虱颗。

• 為什么可以這樣高效的得出新位置呢沥匈？

• 因為擴(kuò)容是容量翻倍，所以原鏈表上的每個節(jié)點忘渔，可能存放新哈希表中在原來的下標(biāo)位置高帖， 或者擴(kuò)容后的原位置偏移量為 oldCap 的位置上

• 圖中，（a）表示擴(kuò)容前的key1和key2兩種key確定索引位置的示例畦粮，（b）表示擴(kuò)容后key1和key2兩種key確定索引位置的示例散址，其中hash1是key1對應(yīng)的哈希與高位運算結(jié)果。

  
  
  image

元素在重新計算hash之后宣赔，因為n變?yōu)?倍预麸，那么n-1的mask范圍在高位多1bit(紅色)，因此新的index就會發(fā)生這樣的變化：

image

所以在 JDK1.8 中擴(kuò)容后儒将，只需要看看原來的hash值新增的那個bit是1還是0就好了吏祸，是0的話索引沒變，是1的話索引變成“原索引+oldCap

• 另外還需要注意的一點是 HashMap 在 1.7的時候擴(kuò)容后钩蚊，鏈表的節(jié)點順序會倒置贡翘，1.8則不會出現(xiàn)這種情況。

7 HashMap 其他添加元素的方法

7.1 putAll

public void putAll(Map<? extends K, ? extends V> m) {
   putMapEntries(m, true);
}

7.2 putMapEntries

//同樣第二參數(shù)代表是否初次創(chuàng)建 table 
 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
   int s = m.size();
   if (s > 0) {
        //如果哈希表為空則初始化參數(shù)擴(kuò)容閾值
       if (table == null) { // pre-size
           float ft = ((float)s / loadFactor) + 1.0F;
           int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                    (int)ft : MAXIMUM_CAPACITY);
           if (t > threshold)
               threshold = tableSizeFor(t);
       }
       else if (s > threshold)//構(gòu)造方法沒有計算 threshold 默認(rèn)為0 所以會走擴(kuò)容函數(shù)
           resize();
        //將參數(shù)中的 map 鍵值對一次添加到 HashMap 中
       for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
           K key = e.getKey();
           V value = e.getValue();
           putVal(hash(key), key, value, false, evict);
       }
   }
}

7.3 putIfAbsent

JDK1.8 中還新增了一個添加方法砰逻，該方法調(diào)用 putVal 且第4個參數(shù)傳了 true鸣驱，代表只有哈希表中對應(yīng)的key 的位置上元素為空的時候添加成功，否則返回原來 key 對應(yīng)的 Value 值蝠咆。

@Override
public V putIfAbsent(K key, V value) {
   return putVal(hash(key), key, value, true, true);
}

8 HashMap 查詢元素

分析了完了 put 函數(shù)后踊东，接下來讓我們看下 get 函數(shù)，當(dāng)然有 put 函數(shù)計算鍵值對在哈希表中位置的索引方法分析的鋪墊后刚操，get 方法就顯得很容容易了闸翅。

8.1 根據(jù)鍵值對的 key 去獲取對應(yīng)的 Value

public V get(Object key) {
   Node<K,V> e;
   //通過 getNode尋找 key 對應(yīng)的 Value 如果沒找到，或者找到的結(jié)果為 null 就會返回null 否則會返回對應(yīng)的 Value
   return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
   Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
   //現(xiàn)根據(jù) key 的 hash 值去找到對應(yīng)的鏈表或者紅黑樹
   if ((tab = table) != null && (n = tab.length) > 0 &&
       (first = tab[(n - 1) & hash]) != null) {
       // 如果第一個節(jié)點就是那么直接返回
       if (first.hash == hash && // always check first node
           ((k = first.key) == key || (key != null && key.equals(k))))
           return first;
        //如果 對應(yīng)的位置為紅黑樹調(diào)用紅黑樹的方法去尋找節(jié)點   
       if ((e = first.next) != null) {
           if (first instanceof TreeNode)
               return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            //遍歷單鏈表找到對應(yīng)的 key 和 Value   
           do {
               if (e.hash == hash &&
                   ((k = e.key) == key || (key != null && key.equals(k))))
                   return e;
           } while ((e = e.next) != null);
       }
   }
   return null;
}

8.2 JDK 1.8新增 get 方法赡茸，在尋找 key 對應(yīng) Value 的時候如果沒找大則返回指定默認(rèn)值

@Override
public V getOrDefault(Object key, V defaultValue) {
   Node<K,V> e;
   return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}

9 HashMap 的刪操作

• HashMap 沒有 set 方法缎脾，如果想要修改對應(yīng) key 映射的 Value ，只需要再次調(diào)用 put 方法就可以了占卧。

9.1 remove(Object key)

 public V remove(Object key) {
   Node<K,V> e;
   return (e = removeNode(hash(key), key, null, false, true)) == null ?
       null : e.value;
}

9.2 remove(Object key, Object value)

@Override
public boolean remove(Object key, Object value) {
   //這里傳入了value 同時matchValue為true
   return removeNode(hash(key), key, value, true, true) != null;
}

9.3 removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable)

這里有兩個參數(shù)需要我們提起注意：

• matchValue 如果這個值為 true 則表示只有當(dāng) Value 與第三個參數(shù) Value 相同的時候才刪除對一個的節(jié)點
• movable 這個參數(shù)在紅黑樹中先刪除節(jié)點時候使用 true 表示刪除并其他數(shù)中的節(jié)點遗菠。

 final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
   Node<K,V>[] tab; Node<K,V> p; int n, index;
   //判斷哈希表是否為空，長度是否大于0 對應(yīng)的位置上是否有元素
   if ((tab = table) != null && (n = tab.length) > 0 &&
       (p = tab[index = (n - 1) & hash]) != null) {
       
       // node 用來存放要移除的節(jié)點华蜒， e 表示下個節(jié)點 k 辙纬，v 每個節(jié)點的鍵值
       Node<K,V> node = null, e; K k; V v;
       //如果第一個節(jié)點就是我們要找的直接賦值給 node
       if (p.hash == hash &&
           ((k = p.key) == key || (key != null && key.equals(k))))
           node = p;
       else if ((e = p.next) != null) {
            // 遍歷紅黑樹找到對應(yīng)的節(jié)點
           if (p instanceof TreeNode)
               node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
           else {
                //遍歷對應(yīng)的鏈表找到對應(yīng)的節(jié)點
               do {
                   if (e.hash == hash &&
                       ((k = e.key) == key ||
                        (key != null && key.equals(k)))) {
                       node = e;
                       break;
                   }
                   p = e;
               } while ((e = e.next) != null);
           }
       }
       // 如果找到了節(jié)點
       // !matchValue 是否不刪除節(jié)點
       // (v = node.value) == value ||
                            (value != null && value.equals(v))) 節(jié)點值是否相同，
       if (node != null && (!matchValue || (v = node.value) == value ||
                            (value != null && value.equals(v)))) {
           //刪除節(jié)點                 
           if (node instanceof TreeNode)
               ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
           else if (node == p)
               tab[index] = node.next;
           else
               p.next = node.next;
           ++modCount;
           --size;
           afterNodeRemoval(node);
           return node;
       }
   }
   return null;
}

10 HashMap 的迭代器

public void test(){

    Map<String, Integer> map = new HashMap<>();
    
    ...
    
    Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
    
    //通過迭代器：先獲得 key-value 對（Entry）的Iterator叭喜，再循環(huán)遍歷   
    Iterator iter1 = entrySet.iterator();
    while (iter1.hasNext()) {
    // 遍歷時贺拣，需先獲取entry，再分別獲取key、value
    Map.Entry entry = (Map.Entry) iter1.next();
    System.out.print((String) entry.getKey());
    System.out.println((Integer) entry.getValue());
    }
}

通過上述遍歷過程我們可以使用 map.entrySet() 獲取之前我們最初提及的 entrySet

public Set<Map.Entry<K,V>> entrySet() {
   Set<Map.Entry<K,V>> es;
   return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

// 我們來看下 EntrySet 是一個 set 存儲的元素是 Map 的鍵值對
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
   // size 放回 Map 中鍵值對個數(shù)
   public final int size()                 { return size; }
   //清除鍵值對
   public final void clear()               { HashMap.this.clear(); }
   // 獲取迭代器
   public final Iterator<Map.Entry<K,V>> iterator() {
       return new EntryIterator();
   }
   
   //通過 getNode 方法獲取對一個及對應(yīng) key 對應(yīng)的節(jié)點 這里必須傳入
   // Map.Entry 鍵值對類型的對象 否則直接返回 false
   public final boolean contains(Object o) {
       if (!(o instanceof Map.Entry))
           return false;
       Map.Entry<?,?> e = (Map.Entry<?,?>) o;
       Object key = e.getKey();
       Node<K,V> candidate = getNode(hash(key), key);
       return candidate != null && candidate.equals(e);
   }
   // 滴啊用之前講得 removeNode 方法 刪除節(jié)點
   public final boolean remove(Object o) {
       if (o instanceof Map.Entry) {
           Map.Entry<?,?> e = (Map.Entry<?,?>) o;
           Object key = e.getKey();
           Object value = e.getValue();
           return removeNode(hash(key), key, value, true, true) != null;
       }
       return false;
   }
   ...
}

//EntryIterator 繼承自 HashIterator
final class EntryIterator extends HashIterator
   implements Iterator<Map.Entry<K,V>> {
   // 這里可能是因為大家使用適配器的習(xí)慣添加了這個 next 方法
   public final Map.Entry<K,V> next() { return nextNode(); }
}

   
abstract class HashIterator {
        Node<K,V> next;        // next entry to return
        Node<K,V> current;     // current entry
        int expectedModCount;  // for fast-fail
        int index;             // current slot

        HashIterator() {
            //初始化操作數(shù) Fast-fail 
            expectedModCount = modCount;
            // 將 Map 中的哈希表賦值給 t
            Node<K,V>[] t = table;
            current = next = null;
            index = 0;
            //從table 第一個不為空的 index 開始獲取 entry
            if (t != null && size > 0) { // advance to first entry
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }
        
        public final boolean hasNext() {
            return next != null;
        }

        final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
             //如果當(dāng)前鏈表節(jié)點遍歷完了譬涡，則取哈希桶下一個不為null的鏈表頭   
            if ((next = (current = e).next) == null && (t = table) != null) {
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }
        //這里還是調(diào)用 removeNode 函數(shù)不在贅述
        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

除了 EntryIterator 以外還有 KeyIterator 和 ValueIterator 也都繼承了HashIterator 也代表了 HashMap 的三種不同的迭代器遍歷方式闪幽。

final class KeyIterator extends HashIterator
   implements Iterator<K> {
   public final K next() { return nextNode().key; }
}

final class ValueIterator extends HashIterator
   implements Iterator<V> {
   public final V next() { return nextNode().value; }
}

可以看出無論哪種迭代器都是通過，遍歷 table 表來獲取下個節(jié)點涡匀，來遍歷的盯腌，遍歷過程可以理解為一種深度優(yōu)先遍歷，即優(yōu)先遍歷鏈表節(jié)點（或者紅黑樹）陨瘩，然后在遍歷其他數(shù)組位置腕够。

11 HashTable 的區(qū)別

面試的時候面試官總是問完 HashMap 后會問 HashTable 其實 HashTable 也算是比較古老的類了。翻看 HashTable 的源碼可以發(fā)現(xiàn)有如下區(qū)別：

1. HashMap 是線程不安全的舌劳，HashTable是線程安全的帚湘。
2. HashMap 允許 key 和 Vale 是 null，但是只允許一個 key 為 null,且這個元素存放在哈希表 0 角標(biāo)位置甚淡。 HashTable 不允許key大诸、value 是 null
3. HashMap 內(nèi)部使用hash(Object key)擾動函數(shù)對 key 的 hashCode 進(jìn)行擾動后作為 hash 值。HashTable 是直接使用 key 的 hashCode() 返回值作為 hash 值材诽。
4. HashMap默認(rèn)容量為 2^4 且容量一定是 2^n ; HashTable 默認(rèn)容量是11,不一定是 2^n
5. HashTable 取哈希桶下標(biāo)是直接用模運算,擴(kuò)容時新容量是原來的2倍+1底挫。HashMap 在擴(kuò)容的時候是原來的兩倍，且哈希桶的下標(biāo)使用 &運算代替了取模脸侥。

參考

搞懂 Java HashMap 源碼