1. HashMap的家族定位

接口java.util.Map有四個常用的實現類，如圖是它們之間的類繼承關係。

下面我將一一介紹其性能特點。

• HashMap：

  • 最常用的Map實現類，通過使用Hash表結構，提高查找速度；
  • 使用鍵值對作為存儲節點，只允許一個key值為null，允許多個value值為null；
  • 線程不安全，對於線程安全有要求的程序，可以考慮使用：sychronizedMap或者ConcurrentHashMap；

• HashTable

  • 同樣使用Hash表結構，提高查找效率；
  • 線程安全，但是安全層級低於ConcurrentHashMap，不常用。

• LinkedHashMap

  • 繼承自HashMap，使用Hash表結構，提高查找效率；
  • 鏈表插入維持插入順序。

• TreeMap

  • sortedMap接口的實現類，可使用特定的排序規則對鍵值對進行排序；

對四種常見的實現類的性能比較如下圖所示：

2. HashMap的數據結構

2.1 Hash表的基本概念

Hash表是數據結構和算法課程中學習到的一種重要的數據結構。主要設計思想是：

• 使用一個長度為n的數組存儲相關數據。

• 使用hash函數實現內容和數組下標的對應，也就是hash函數的函數值為0~n之間。

  • hash函數相同的輸入參數一定會產生相同函數值，不同內容儘量做到函數值分散。
• 在hash函數值對應的下標寫入該內容。
• 下次查找某元素的時候，先根據hash函數生成下標，然後再隨機訪問數組，這樣查找效率大大提高了。

類似於一個叫賈斯汀·費爾蘭德·亨利皮特潘（複雜內容）的人，在酒店前台（hash函數）入住酒店的房間編號是1004（hash函數值/數組下標）。需要找他的人，只需要去酒店前台查詢他住在1004房間，直接去1004房間找人就可以了，不需要一個一個房間去找。

2.2 Hash衝突

在上面的流程説明中，我們可以發現Hash表的實現關鍵就在於Hash函數，一個好的hash函數應該保證不同的輸入內容儘量分散其函數值。
當存入的數據過多，hash函數性能較差的時候，可能會出現hash衝突：

• A和B是兩個不同的存儲內容，但是經過hash函數計算，得到的hash函數值相同，因此兩個內容存儲在數組的同一位置。
• 例如：賈斯汀·費爾蘭德·亨利皮特潘和特朗普·懂王·建國同志兩個人在酒店前台分配到的房間號都是1004，但是房間只有一張牀，這時兩個人就會發生衝突。

解決衝突主要有兩種思路：

• 開放定址法：發生衝突的時候，後到來的元素放棄已被佔用的位置，尋找新的插入位置。（再找）

• 鏈地址法：發生衝突的時候，後到來的元素在原有位置的基礎上，使用鏈表的方式存儲。（排隊）

  • HashMap使用的就是鏈地址法。

2.3 HashMap數據結構

1. 節點Node
   Node是HashMap的一個基本存儲單元，從源碼中可見Node實現了Map.Entry接口，存放的是鍵值對。在JDK1.8中的源碼中，Node的定義如下所示：

   static class Node<K,V> implements Map.Entry<K,V> {
       final int hash;    //用來定位數組索引位置
       final K key;
       V value;
       Node<K,V> next;   //鏈表的下一個node
   
       Node(int hash, K key, V value, Node<K,V> next) { ... }
       public final K getKey(){ ... }
       public final V getValue() { ... }
       public final String toString() { ... }
       public final int hashCode() { ... }
       public final V setValue(V newValue) { ... }
       public final boolean equals(Object o) { ... }
   }

2. JDK1.7的HashMap數據結構
   數組+鏈表

   • 如圖所示
     
   • 使用鏈地址方式解決hash衝突。

3. JDK1.8的HashMap數據結構
   數組+鏈表+紅黑樹

   • 如圖所示

     ![在這裏插入圖片描述](https://img-blog.csdnimg.cn/e80970c484d9427c8c47885eabbe0229.png#pic_center)
     

   • 對紅黑樹的學習可參考此博客。
   • 鏈表和紅黑樹的轉換根據鏈表長度閾值判斷，閾值為8，即鏈表長度大於8時，由鏈表轉換為紅黑樹，小於6時，由紅黑樹轉換為鏈表。
   • 紅黑樹的引入目的：在鏈表長度較長的情況下，優化查找效率。

3. HashMap的重要變量

3.1 常量

• DEFAULT_INITIAL_CAPACITY

  • 默認的數組初始容量，值為2^4=16。
  • 如果沒有指定初始數組的容量的話，就會使用這個默認值。

• MAXIMUM_CAPACITY

  • 最大的數組容量，值為2^30。
  • 在擴容的時候，如果擴容後的容量大於這個值，就會使用這個值作為新的容量。
  • 之後如果數據再增加，不再進行擴容，而是直接鏈表存儲或者轉為紅黑樹。

• DEFAULT_LOAD_FACTOR

  • 默認負載因子，值為0.75。
  • 在HashMap中，擴容的臨界值計算公式為：
    臨界值（threshold） = 負載因子（loadFactor） * 容量（capacity）

  • 負載因子可以設置為任意值，但是需要注意的是：

    • 負載因子變大，hash衝突的概率就會變大，查找效率就會降低。【犧牲時間】
    • 負載因子過小，會導致數組空間利用率低，浪費內存空間。【犧牲空間】

• TREEIFY_THRESHOLD

  • 鏈表轉化為紅黑樹的閾值，值為8。
  • 當一個數組節點所帶着的鏈表長度大於8時，鏈表會轉化為紅黑樹。

• UNTREEIFY_THRESHOLD

  • 紅黑樹轉化為鏈表的閾值，值為6。
  • 當一個數組節點的紅黑樹節點小於6時，紅黑樹會轉化為鏈表。

• MIN_TREEIFY_CAPACITY

  • 轉換為紅黑樹的最小容量，值為64。

  • 這個變量的意思是，在HashMap不斷增加新元素的過程中，如果此時數組中的元素個數小於64，那麼就選擇擴容。當數組元素個數大於64的時候才會考慮樹化。

    3.2 變量

• size

  • HashMap中存儲的鍵值對個數。

• modCount

  • 對HashMap進行修改的次數記錄，每次增刪則加一。

• threshold

  • 擴容的臨界值，計算公式為：threshold = loadFactor * capacity。其中capacity為數組總長度，通常為了提高閾值，會使用擴容增加capacity，而對於負載因子loadFactor，一般不會修改。

• loadFactor

  • 負載因子，用户可自行設置其值，否則等於默認值0.75。

3.3 辨析size、capacity、threshold

size:實際存儲的鍵值對個數
capacity:數組的總長度
threshold:擴容的臨界值
treeify_threshold/untreeify_threahold:鏈表和紅黑樹相互轉化的閾值

4. HashMap重要方法和源碼解析

4.1 構造方法

1. HashMap()
   無參構造，使用默認的初始容量2^4和負載因子0.75，構造一個空的HashMap。

   // 構造一個空的 HashMap，初始容量為 16，負載因子為默認值 0.75
   public HashMap() {    
    this.loadFactor = DEFAULT_LOAD_FACTOR;  // all other fields defaulted
   }

2. HashMap(int initialCapacity)
   指定初始容量，使用默認的負載因子0.75。

   public HashMap(int initialCapacity) {    
    this(initialCapacity, DEFAULT_LOAD_FACTOR);//一次性實現容量和負載因子的賦值
   }
   

3. HashMap(int initialCapacity, float loadFactor)
   指定初始容量和負載因子，構造一個空的HashMap。

   public HashMap(int initialCapacity, float loadFactor) {
    // 如果初始容量為負數，拋出非負異常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +  initialCapacity);
    // 初始容量大於最大值時1<<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);//tableSizeFor() 方法返回一個值，比initialCapacity大的最小2的冪。
   }

4. HashMap(Map<? extends K, ? extends V> m)
   構造一個非空的HashMap，將m中的鍵值對存入HashMap中，默認的負載因子 0.75，使用默認的初始容量2^4。

   public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    // 將 Map 中的 key-value 賦值到新的 Map 中去
    putMapEntries(m, false);
   }
   

   4.2 resize方法

   當HashMap中數組的使用量超過閾值的時候，就需要進行擴容。JDK1.8的源碼如下所示：

   final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;// 當前 table
    int oldCap = (oldTab == null) ? 0 : oldTab.length;// 當前table的大小
    int oldThr = threshold;// 當前 table 的 threshold
    int newCap, newThr = 0;// 新的 table 的大小和閥值暫時初始化為 0
   
    // 下面就是開始計算新的 table 的大小和閥值
    // 第一種情況：當前 table 的大小大於 0，則意味着當前的 table 肯定是有數據的
    if (oldCap > 0) {//
        if (oldCap >= MAXIMUM_CAPACITY) {//原始容量大於最大容量，不再擴容，直接返回原始table
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)//翻倍之後不超過最大容量，原始容量小於最大容量，且大於默認容量，那麼容量翻倍，閾值也對應翻倍
            newThr = oldThr << 1;
    }
    // 第二種情況：當前的 table 中無數據，但是閥值不為零，説明初始化的時候指定過容量或者閥值，但是沒有被 put 過數據，
    else if (oldThr > 0) 
        newCap = oldThr;//此時的閥值就是數組的大小，所以直接把當前的閥值當做新 table 的數組大小即可。threshold = tableSizeFor(t);
    // 第三種情況，這種情況就代表當前的 table 是調用的空參構造來初始化的，所有的數據都是默認值。
    else {//初始閾值為0，表示使用默認值，新的 table 也只要使用默認值即可
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果新的閥值是 0，那麼就簡單計算一遍就行了
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
   
    // 根據上文中計算的新表容量和閾值，初始化新的 table
    // 這個 newTab 就是新的 table，數組大小就是上面這一堆邏輯所計算出來的
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 遍歷當前 table，處理每個下標處的 bucket，將其處理到新的 table 中去
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 釋放當前 table 數組的對象引用（for循環後，當前 table 數組不再引用任何對象）
                oldTab[j] = null;
                // a、只有一個 Node，則直接 rehash 賦值即可
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // b、當前的 bucket 是紅黑樹，直接進行紅黑樹的 rehash 即可
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // c、當前的 bucket 是鏈表
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 遍歷鏈表中的每個 Node，分別判斷是否需要進行 rehash 操作
                    // (e.hash & oldCap) == 0 算法是精髓，充分運用了上文提到的 table 大小為 2 的冪次方這一優勢，下文會細講
                    do {
                        next = e.next;
                        // 根據 e.hash & oldCap 算法來判斷節點位置是否需要變更
                        // 索引不變
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 原索引 + oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原 bucket 位置的尾指針不為空(即還有 node )
                    if (loTail != null) {
                        // 鏈表末尾必須置為 null
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        // 鏈表末尾必須置為 null
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
   }

5. 為什麼要*2擴容？或者説，為什麼HashMap的數組大小為2的冪
   在理論學習中，Hash表的大小最好是素數，因為素數能夠有效降低hash碰撞。但是HashMap並沒有採用這種做法。
   在上面的源碼中，我們可以看到，HashMap在擴容的時候，數組的大小都是原來的兩倍，這是因為在計算索引的時候，我們使用的是size-1的n個全1二進制串和hash值進行與運算，這樣可以保證計算出來的索引值一定在0~size-1之間，不會越界。如圖所示：
   

當HashMap值為2的冪的時候，size-1為全1二進制字符串，且擴容之後，原本有衝突的兩個元素會找到各自的新索引位置。如圖所示：

在代碼中，這個步驟被進一步簡化。如代碼片段所示：

if ((e.hash & oldCap) == 0) {
  if (loTail == null)
      loHead = e;
  else
      loTail.next = e;
  loTail = e;
}
// 原索引 + oldCap
else {
  if (hiTail == null)
      hiHead = e;
  else
      hiTail.next = e;
  hiTail = e;
}

因為hash值是一個整數，所以hash & oldCap的結果要麼是0，要麼是oldCap。所以，hashMap的擴容，實際上是將原來的數組分成兩部分，一部分的索引不變，一部分的索引變為原索引+oldCap。這樣就保證了原來的兩個元素，擴容之後，一定不會在同一個索引位置上。具體解釋如圖所示：

4.3 hash方法

也就是之前在理論部分所説的hash函數部分，將關鍵字key的值轉換為唯一hash值，JDK1.8源碼如下:

static final int hash(Object key) {
    int h;
    // 高 16 位與低 16 位進行異或運算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hashCode()函數通常和equals()函數進行比較，hashCode()函數是根據對象的內存地址生成一個特定的數，因此，hashCode值相同的對象不一定相同，hashCode值不同的對象一定不相同。
一般判斷兩個對象是否相等，先使用hashCode()函數判斷內存地址，如果hashCode()函數值相同，再使用equals()函數判斷內存中的內容，如果hashCode()函數值不同，就不需要再使用equals()函數判斷了。

這裏h先設置成key值的hashCode，然後右移16位，再和原來的h進行異或運算，這樣做的目的是為了減少hash碰撞，提高查找效率。

之後如何從hash值映射到數組下標，在JDK1.7的源碼如下所示:

static int indexFor(int h, int length) {
    return h & (length-1);
}

這裏也解釋了為什麼HashMap的數組大小為2的冪，因為這樣可以保證length-1為全1的二進制串，與操作之後計算出來的索引值一定在0~size-1之間，不會越界，具體操作如圖所示：

4.4 put方法

put方法主要是在HashMap中存儲鍵值對，JDK1.8源碼如下所示：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);//重點在於putVal方法
}

// 參數 onlyIfAbsent,針對已經存在的value，值為true表示不修改；否則表示會替換原本的value值
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 為空則進行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash 計算得到索引 i，算法在上文有提到，然後查看索引處是否有數據
    // ② 如果沒有數據，則新建一個新的 Node
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 索引處有數據
    else {
        Node<K,V> e; K k;
        // ③ 索引處的第一個 Node 的  key 和參數 key 是一致的，所以直接修改 value 值即可（修改的動作放在下面）
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // ④ 索引處的 bucket 是紅黑樹，按照紅黑樹的邏輯進行插入或修改
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // ⑤ 索引處的 bucket 是鏈表
        else {
            // 遍歷鏈表上面的所有 Node
            for (int binCount = 0; ; ++binCount) {
                // 索引處的 Node 為尾鏈
                if ((e = p.next) == null) {
                    // 直接新建一個 Node 插在尾鏈處
                    p.next = newNode(hash, key, value, null);
                    // 判斷是否需要轉換為紅黑樹
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 鏈表轉換為紅黑樹，此方法在上文中也有介紹
                        treeifyBin(tab, hash);
                    break;
                }
                // 當前 Node 的 key 值和參數 key 是一致的，即直接修改 value 值即可（修改的動作放在下面）
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 找到了相同 key 的 Node，所以進行修改 vlaue 值即可
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // 修改 value 值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            // 修改操作，直接 return 結束掉代碼邏輯
            return oldValue;
        }
    }
    // 記錄結構發生變化的次數
    ++modCount;
    // ⑥ 判斷是否需要擴容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    // 新增的 Node，返回 null
    return null;
}

源代碼所抽象出來的具體的put流程可如下圖所示：

在JDK1.7中，鏈表插入使用頭插法，而在JDK1.8中，鏈表插入使用尾插法，

• JDK1.7 使用頭插法的原因：考慮到熱點數據，後面插入的元素更有可能被最近使用，因此使用頭插法。
• 頭插法會使鏈表上 Node 的順序調轉，而尾插法則不會，另外，頭插法也會造成環形鏈死循環等問題，

• 參考文獻

• 知乎專欄-HashMap原理詳解，看不懂算我輸（附面試題）
• 掘金社區-詳解 HashMap 數據結構
• 美團技術團隊-Java 8系列之重新認識HashMap