我是風箏，公眾號「古時的風箏」，一個兼具深度與廣度的程序員鼓勵師，一個本打算寫詩卻寫起了代碼的田園碼農！
文章會收錄在 JavaNewBee 中，更有 Java 後端知識圖譜，從小白到大牛要走的路都在裏面。

這是上篇文章 有趣的條漫版 HashMap，25歲大爺都能看懂 的文字版。有不少同學說條漫版的比較有意思，簡單易懂，但是畢竟圖片畫不了那麼詳細，只能從大面而上理解。

真正的了解細節，還得看這一篇。其實是這篇先寫完，然後畫了不少圖片，所以就寫了一篇圖片版的。本篇 7000 多字，建議三連呦。

在 Java 中，最常用的數據類型是 8 中基本類型以及他們的包裝類型以及字符串類型，其次應該就是 ArrayList和HashMap了吧。HashMap存的是鍵值對類型的數據，其存儲和獲取的速度快、性能高，是非常好用的一個數據結構，每一個 Java 開發者都肯定用過它。

而且 HashMap的設計巧妙，其結構和原理也經常被拿去當做面試題。其中有很多巧妙的算法和設計，比如 Hash 算法、拉鏈法、紅黑樹設計等，值得每一個開發者借鑒學習。

想了老半天，怎麼才能簡單易懂的把 HashMap說明白呢，那就從我理解它的思路和過程去說吧。要理解一個事物最好的方式就是先了解整體結構，再去追究細節。所以，我們先從結構談起。

先從結構說起

拿我自身的一個體會來說吧，風箏我作為一個專業路痴，對於迷路這件事兒絕不含糊，雖然在北京混跡多年，但是只在中關村能分清南北，其他地方，哪怕是我每天住的小區、每天工作的公司也分不太清方向，回家只能認一條路，要是打車換條路回家，也得迷糊一陣，這麼說吧，在小區前面能回家，小區後面找不到家。去個新地方，得盯着地圖看半天。這時，我就在想啊，要是我能在城市上空俯瞰下面的街道，那我就再也不怕找不到回家的路了。這不就是三體里的降維打擊嗎，站在高維的立場，理解低維的事物，那就簡單多了。

理解數據結構也是一個道理，大多數時候，我們都是停留在會用的層面上，理解一些原理也只是支離破碎的，困在數據機構的迷宮裡跌跌撞撞，迫切的需要一張地圖或者一架直升機。

先來看一下整個 Map家族的集成關係圖，一看東西還不少，但其他的可能都沒怎麼用過，只有 HashMap最熟悉。

以下描述可能不夠專業，只為簡單的描述 HashMap的結構，請結合下圖進行理解。

HashMap主體上就是一個數組結構，每一個索引位置英文叫做一個 bin，我們這裏先管它叫做桶，比如你定義一個長度為 8 的 HashMap，那就可以說這是一個由 8 個桶組成的數組。當我們像數組中插入數據的時候，大多數時候存的都是一個一個 Node 類型的元素，Node 是 HashMap中定義的靜態內部類。

當插入數據（也就是調用 put 方法）的時候，並不是按順序一個一個向後存儲的，HashMap中定義了一套專門的索引選擇算法，叫做散列計算，但散列計算存在一種情況，叫哈希碰撞，也就是兩個不一樣的 key 散列計算出來的 hash 值是一致的，這種情況怎麼辦呢，採用拉鏈法進行擴展，比如圖中藍色的鏈表部分，這樣一來，具有相同 hash 值的不同 key 即可以落到相同的桶中，又保證不會覆蓋之前的內容。

但隨着插入的元素越來越多，發生碰撞的概率就越大，某個桶中的鏈表就會越來越長，直到達到一個閾值，HashMap就受不了了，為了提升性能，會將超過閾值的鏈錶轉換形態，轉換成紅黑樹的結構，這個閾值是 8 。也就是單個桶內的鏈表節點數大於 8 ，就會將鏈表變身為紅黑樹。

以上概括性的描述就是 HashMap的整體結構，也是我們進一步研究細節的藍圖。我們將從中抽取出幾個關鍵點一一解釋，從整體到細節，降維打擊 HashMap。

接下來就是說明為什麼會設計成這樣的結構以及從單純數組到桶內鏈表產生，接着把鏈錶轉換成紅黑樹的詳細過程。

認清幾個關鍵概念

存儲容器

因為HashMap內部是用一個數組來保存內容的，數組定義如下：

transient Node<K,V>[] table;

Node 類型

table 是一個 Node類型的數組，Node是其中定義的靜態內部類，主要包括 hash、key、value 和 next 的屬性。比如之後我們使用 put 方法像其中加鍵值對的時候，就會轉換成 Node 類型。

static class Node<K,V> implements Map.Entry<K,V> {
  final int hash;
  final K key;
  V value;
  Node<K,V> next;
}

TreeNode

前面說了，當桶內鏈表到達 8 的時候，會將鏈錶轉換成紅黑樹，就是 TreeNode類型，它也是 HashMap中定義的靜態內部類。

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;
}

容量和默認容量

容量就是 table 數組的長度，也就是我們所說的桶的個數。其定義如下

int threshold;

默認是 16，如果我們在初始化的時候沒有指定大小，那就是 16。當然我們也可以自己指定初始大小，而 HashMap 要求初始大小必須是 2 的 冪次方。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

元素個數

容量是指定了桶的個數，而 size 是說 HashMap中實際存了多少個鍵值對。

transient int size;

最大容量

table 的長度也是有限制的，不能無限大，HashMap規定最大長度為 2 的30次方。

static final int MAXIMUM_CAPACITY = 1 << 30;

負載因子

這是一個係數，它和 threshold 結合起作用，默認是 0.75。一般情況下不要改。

final float loadFactor;

擴容閾值

閾值 = 容量 x 負載因子，假設當前 HashMap的容量是 16，負載因子是默認值 0.75，那麼當 size 到達 16 x 0.75= 12 的時候，就會觸發擴容。

初始化 HashMap

使用 HashMap肯定要初始化吧，很多情況下都是用無參構造方法創建。

Map<String,String> map = new HashMap<>();

這種情況下所有屬性都是默認值，比如容量是 16，負載因子是 0.75。

另外推薦的一種初始化方式，就是給定一個默認容量，比如指定默認容量是 32。

Map<String,String> map = new HashMap<>(32);

但是 HashMap 要求初始大小必須是 2 的 n 次方，但是又不能要求每個開發人員指定初始容量的時候都按要求來，比如我們指定初始大小為為 7、18 這種會怎麼樣呢？

沒關係，HashMap中有個方法專門負責將傳過來的參數值轉換為最接近、且大於等於指定參數的 2 的 n 次方的值，比如指定大小為 7 的話，最後實際的容量就是 8 ，如果指定大小為 18的話，那最後實際的容量就是 32 。

public HashMap(int initialCapacity, float loadFactor) {
  if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal initial capacity: " +
                                       initialCapacity);
  if (initialCapacity > MAXIMUM_CAPACITY)
    initialCapacity = MAXIMUM_CAPACITY;
  if (loadFactor <= 0 || Float.isNaN(loadFactor))
    throw new IllegalArgumentException("Illegal load factor: " +
                                       loadFactor);
  this.loadFactor = loadFactor;
  this.threshold = tableSizeFor(initialCapacity);
}

執行這個轉換動作的就是 tableSizeFor方法，經過轉換后，將最終的結果賦值給 threshold變量，也就是初始容量，也就是本篇中所說的桶個數。

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;
  return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

tableSizeFor這個方法就有意思了，先把初始參數減 1，然後連着做或等於和無符號右移操作，最後算出一個接近的 2 的冪次方，下圖演示了初始參數為 18 時的一系列操作，最後得出的初始大小為 32。

這個算法很有意思了，比如你給的初始大小是 63，那得到的結果就是 64，如果初始大小給定 65 ，那得到的結果就是 128，總是能得出不小於給定初始大小，並且最接近的2的n次方的最終值。

從 put 方法解密核心原理

put方法是增加鍵值對最常用的方法，也是最複雜的過程，增加鍵值對的過程涉及了 HashMap最核心的原理，主要包括以下幾點：

1. 什麼情況下會擴容，擴容的規則是什麼？
2. 插入鍵值對的時候如何確定索引，HashMap可不是按順序插入的，那樣不就真成了數組了嗎。
3. 如何確保 key 的唯一性？
4. 發生哈希碰撞怎麼處理？
5. 拉鏈法是什麼？
6. 單桶內的鏈表如何轉變成紅黑樹？

以下是 put 方法的源碼，我在其中做了註釋。

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) {
  HashMap.Node<K,V>[] tab; // 聲明 Node 數組 tab
  HashMap.Node<K,V> p;    // 聲明一個 Node 變量 p
  int n, i;
  /**
  * table 定義 transient Node<K,V>[] table; 用來存儲 Node 節點
  * 如果 當前table為空，則調用resize() 方法分配數組空間
  */
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  // n 總是為 2 的冪次方，(n-1) & hash 可確定 tab.length （也就是table數組長度）內的索引
  // 然後 創建一個 Node 節點賦給當前索引
  if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  else {
    //如果當前索引位置已經有值了，怎麼辦
    // 拉鏈法出場
    HashMap.Node<K,V> e;
    K k;
    // 判斷 key 值唯一性
    // p 是當前待插入索引處的值
    // 哈希值一致並且（當前位置的 key == 待插入的key(注意 == 符號)，或者key 不為null 並且 key.equals(k)）
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k)))) //如果當前節點只有一個元素，且和待插入key一樣 則覆蓋
      // 將 p（當前索引）節點臨時賦予 e
      e = p;
    else if (p instanceof HashMap.TreeNode) // 如果當前索引節點是一顆樹節點
      //插入節點樹中 並返回
      e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
      // 當前索引節點即不是只有一個節點，也不是一顆樹，說明是一個鏈表
      for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) { //找到沒有 next 的節點，也就是最後一個
          // 創建一個 node 賦給 p.next
          p.next = newNode(hash, key, value, null);
          // 如果當前位置+1之後大於 TREEIFY_THRESHOLD 則要進行樹化
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            //執行樹化操作
            treeifyBin(tab, hash);
          break;
        }
        //如果又發生key衝突則停止 後續這個節點會被相同的key覆蓋
        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)
        e.value = value;
      afterNodeAccess(e);
      return oldValue;
    }
  }
  ++modCount;
  // 當實際長度大於 threshold 時 resize
  if (++size > threshold)
    resize();
  afterNodeInsertion(evict);
  return null;
}

首次初始化數組和擴容

在執行 put方法時，第一步要檢查 table 數組是否為空或者長度是否為 0，如果是這樣的，說明這是首次插入鍵值對，需要執行 table 數組初始化操作。

另外，隨之鍵值對添加的越來越多，HashMap的 size 越來越大，注意 size 前面說了，是實際的鍵值對數量，那麼 size 到了多少就要擴容了呢，並不是等 size 和 threshold（容量）一樣大了才擴容，而是到了閾值就開始擴容，閾值上面也說了，是容量 x 負載因子。

為什麼放在一起說呢，因為首次初始化和擴容都是用的同一個方法，叫做 resize()。以下是我註釋的 resize()方法。

final HashMap.Node<K,V>[] resize() {
  // 保存 table 副本，接下來 copy 到新數組用
  HashMap.Node<K,V>[] oldTab = table;
  // 當前 table 的容量，是 length 而不是 size
  int oldCap = (oldTab == null) ? 0 : oldTab.length;
  // 當前桶大小
  int oldThr = threshold;

  int newCap, newThr = 0;
  if (oldCap > 0) { //如果當前容量大於 0，也就是非第一次初始化的情況（擴容場景下）
    if (oldCap >= MAXIMUM_CAPACITY) { //不能超過最大允許容量
      threshold = Integer.MAX_VALUE;
      return oldTab;
    }
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY) // 雙倍擴容
      newThr = oldThr << 1; // double threshold
  }
  else if (oldThr > 0) // 初始化的場景（給定默認容量），比如 new HashMap(32)
    newCap = oldThr; //將容量設置為 threshold 的值
  else {               // 無參數初始化場景，new HashMap()
    // 容量設置為 DEFAULT_INITIAL_CAPACITY
    newCap = DEFAULT_INITIAL_CAPACITY;
    // 閾值 超過閾值會觸發擴容
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  if (newThr == 0) { //給定默認容量的初始化情況
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
              (int)ft : Integer.MAX_VALUE);
  }
  // 保存新的閾值
  threshold = newThr;
  // 創建新的擴容后數組，然後將舊的元素複製過去
  @SuppressWarnings({"rawtypes","unchecked"})
  HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
  table = newTab;
  if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {
      HashMap.Node<K,V> e;
      //遍歷 獲得得到元素 賦給 e
      if ((e = oldTab[j]) != null) { //如果當前桶不為空
        oldTab[j] = null; // 置空回收
        if (e.next == null) //節點 next為空的話 重新尋找落點 
          newTab[e.hash & (newCap - 1)] = e;
        else if (e instanceof HashMap.TreeNode) //如果是樹節點
          //紅黑樹節點單獨處理
          ((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        else { // 保持原順序
          HashMap.Node<K,V> loHead = null, loTail = null;
          HashMap.Node<K,V> hiHead = null, hiTail = null;
          HashMap.Node<K,V> next;
          do {
            next = e.next;
            if ((e.hash & oldCap) == 0) {
              if (loTail == null)
                loHead = e;
              else
                loTail.next = e;
              loTail = e;
            }
            else {
              if (hiTail == null)
                hiHead = e;
              else
                hiTail.next = e;
              hiTail = e;
            }
          } while ((e = next) != null);
          if (loTail != null) {
            loTail.next = null;
            newTab[j] = loHead;
          }
          if (hiTail != null) {
            hiTail.next = null;
            newTab[j + oldCap] = hiHead;
          }
        }
      }
    }
  }
  return newTab;
}

首次初始化

put方法中線先檢查 table 數組是否為空，如果為空就初始化。

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

首次初始化分為無參初始化和有參初始化兩種情況，前面在講 HashMap初始化的時候說了，無參情況默認就是 16，也就是 table 的長度為 16。有參初始化的時候，首先使用 tableSizeFor()方法確定實際容量，最後 new 一個 Node 數組出來。

HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];

其中 newCap就是容量，默認16或者自定義的。

而這個過程中還有很重要的一步，就是維護擴容閾值。

擴容

put方法中，判斷當 size（實際鍵值對個數）到達 threshold （閾值）時，觸發擴容操作。

// 當實際長度大於 threshold 時 resize
if (++size > threshold)
    resize();

HashMap遵循兩倍擴容規則，每次擴容之後的大小是擴容前的兩倍。另外，說到底，底層的存儲還是一個數組，Java 中沒有真正的動態數組這一說，數組初始化的時候是多大，那它就一直是這麼大，那擴容是怎麼來的呢，答案就是創建一個新數組，然後將老數組的數據拷貝過去。

拷貝的時候可能會有如下幾種情況：

1. 如果節點 next 屬性為空，說明這是一個最正常的節點，不是桶內鏈表，也不是紅黑樹，這樣的節點會重新計算索引位置，然後插入。
2. 如果是一顆紅黑樹，則使用 split方法處理，原理就是將紅黑樹拆分成兩個 TreeNode 鏈表，然後判斷每個鏈表的長度是否小於等於 6，如果是就將 TreeNode 轉換成桶內鏈表，否則再轉換成紅黑樹。
3. 如果是桶內鏈表，則將鏈表拷貝到新數組，保證鏈表的順序不變。

確定插入點

當我們調用 put方法時，第一步是對 key 進行 hash 計算，計算這個值是為了之後尋找落點，也就是究竟要插入到 table 數組的哪個桶中。

hash 算法是這樣的，拿到 key 的 hashCode，將 hashCode 做一次16位右位移，然後將右移的結果和 hashCode 做異或運算，這段代碼叫做「擾動函數」，之所以不直接拿 hashCode 是為了增加隨機性，減少哈希碰撞次數。

/**
* 用來計算 key 的 hash 值
**/
static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

拿到這個 hash 值之後，會進行這樣的運算 i = (n - 1) & hash，其中 i就是最終計算出來的索引位置。

有兩個場景用到了這個索引計算公式，第一個場景就是 put方法插入鍵值對的時候。第二個場景是在 resize 擴容的時候，new 出來新數組之後，將已經存在的節點移動到新數組的時候，如果節點不是鏈表，也不是紅黑樹，而是一個普通的 Node 節點，會重新計算，找到在新數組中的索引位置。

接着看圖，還是圖說的清楚。

HashMap 要求容量必須是 2 的 n 次方，2的 n 次方的二進製表示大家肯定都很清楚，2的6次方，就是從右向左 6 個 0，然後第 7 位是 1，下圖展示了 2 的 6 次方的二進製表示。

然後這個 n-1的操作就厲害了，減一之後，後面之前二進製表示中 1 後面的 0 全都變成了 1，1 所在的位變為 0。比如 64-1 變為 63，其二進製表示是下面這樣的。

下圖中，前面 4 行分別列出了當 map 的容量為 8、16、32、64的時候，假設容量為 n，則對應的 n-1 的二進製表示是下面這樣的，尾部一片紅，都是 1 ，能預感到將要有什麼騷操作。

沒錯，將這樣的二進製表示代入這個公式 (n - 1) & hash中，最終就能確定待插入的索引位了。接着看圖最下面的三行，演示了假設當前 HashMap的容量為 64 ，而待插入的一個 key 經過 hash 計算后得到的結果是 99 時，代入公式計算 index 的值，也就是 （64-1）& 99，最終的計算結果是 35，也就是這個 key 會落到 table[35] 這個位置。

為什麼 HashMap一定要保證容量是 2 的冪次方呢，通過二進製表示可以看出，如果有多位是 1 ，那與 hash 值進行與運算的時候，更能保證最後散列的結果均勻，這樣很大程度上由 hash 的值來決定。

如何確保 key 的唯一性

HashMap中不允許存在相同的 key 的，那怎麼保證 key 的唯一性呢，判斷的代碼如下。

if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))

首先通過 hash 算法算出的值必須相等，算出的結果是 int，所以可以用 == 符號判斷。只是這個條件可不行，要知道哈希碰撞是什麼意思，有可能兩個不一樣的 key 最後產生的 hash 值是相同的。

並且待插入的 key == 當前索引已存在的 key，或者 待插入的 key.equals(當前索引已存在的key)，注意== 和 equals 是或的關係。== 符號意味着這是同一個對象， equals 用來確定兩個對象內容相同。

如果 key 是基本數據類型，比如 int，那相同的值肯定是相等的，並且產生的 hashCode 也是一致的。

String 類型算是最常用的 key 類型了，我們都知道相同的字符串產生的 hashCode 也是一樣的，並且字符串可以用 equals 判斷相等。

但是如果用引用類型當做 key 呢，比如我定義了一個 MoonKey 作為 key 值類型

public class MoonKey {

    private String keyTile;

    public String getKeyTile() {
        return keyTile;
    }

    public void setKeyTile(String keyTile) {
        this.keyTile = keyTile;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        MoonKey moonKey = (MoonKey) o;
        return Objects.equals(keyTile, moonKey.keyTile);
    }
}

然後用下面的代碼進行兩次添加，你說 size 的長度是 1 還是 2 呢？

Map<MoonKey, String> m = new HashMap<>();
MoonKey moonKey = new MoonKey();
moonKey.setKeyTile("1");
MoonKey moonKey1 = new MoonKey();
moonKey1.setKeyTile("1");
m.put(moonKey, "1");
m.put(moonKey1, "2");
System.out.println(hash(moonKey));
System.out.println(hash(moonKey1));
System.out.println(m.size());

答案是 2 ，為什麼呢，因為 MoonKey 沒有重寫 hashCode 方法，導致 moonkey 和 moonKey1 的 hash 值不可能一樣，當不重寫 hashCode 方法時，默認繼承自 Object的 hashCode 方法，而每個 Object對象的 hash 值都是獨一無二的。

划重點，正確的做法應該是加上 hashCode的重寫。

@Override
public int hashCode() {
  return Objects.hash(keyTile);
}

這也是為什麼要求重寫 equals 方法的同時，也必須重寫 hashCode方法的原因之一。 如果兩個對象通過調用equals方法是相等的，那麼這兩個對象調用hashCode方法必須返回相同的整數。有了這個基礎才能保證 HashMap或者HashSet的 key 唯一。

發生哈希碰撞怎麼辦

前面剛說了相等的對象產生的 hashCode 也要相等，但是不相等的對象使用 hash方法計算之後也有可能產生相同的值，這就叫做哈希碰撞。雖然通過算法已經很大程度上避免碰撞的發生，但是卻無法避免。

產生碰撞之後，自然得出的在 table 數組的索引（也就是桶）也是一樣的，這時，怎麼辦呢，一個桶里怎麼放多個鍵值對？

拉鏈法

文章剛開頭就提到了，HashMap可不是簡單的數組而已。當碰撞發生就坦然接收。有一種方法叫做拉鏈法，不是衣服上那種拉鏈。而是，當碰撞發生了，就在當前桶上拉一條鏈表出來，這樣解釋就合理了。

前面介紹關鍵概念的時候提到了 Node類型，裏面有個屬性叫做 next，它就是為了這種鏈表設計的，如下圖所示。node1、node2、node3都落在了同一個桶中，這時候就得用鏈表的方式處理了，node1.next = node2，node2.next = node3，這樣將鏈表串起來。而 node3.next = null，則說明這是鏈表的尾巴。

當有新元素準備插入到鏈表的時候，採用的是尾插法，而不是頭插法了，JDK 1.7 的版本採用的是頭插法，但是頭插法有個問題，就是在兩個線程執行 resize() 擴容的時候，很可能造成環形鏈表，導致 get 方法出現死循環。

鏈錶轉換成樹

鏈表不是碰撞處理的終極結構，終極結構是紅黑樹，當鏈表長度到達 8 之後，再有新元素進來，那就要開始由鏈表到紅黑樹的轉換了。方法 treeifyBin是完成這個過程的。

使用紅黑樹是出於性能方面的考慮，紅黑樹的查找速度要優於鏈表。那為什麼不是一開始就直接生成紅黑樹，而是鏈表長度大於 8 之後才升級成樹呢？

首先來說，哈希碰撞的概率還是很小的，大部分情況下都是一個桶裝一個 Node，即便發生碰撞，都碰撞到一個桶的概率那就更是少之又少了，所以鏈表長度很少有機會能到 8 ，如果鏈表長度到 8 了，那說明當前 HashMap中的元素數量已經非常大了，那這時候用紅黑樹來提高性能是可取的。而反過來，如果 HashMap總的元素很少，即便用紅黑樹對性能的提升也不大，況且紅黑樹對空間的使用要比鏈表大很多。

get 方法

T value = map.get(key);

例如通過上面的語句通過 key 獲取 value 值，是我們最常用到的方法了。

看圖理解，當調用 get方法后，第一步還是要確定索引位置，也就是我們所說的桶的位置，方法和 put方法時一樣，都是先使用 hash這個 擾動函數 確定 hash 值，然後用 (n-1) & hash獲取索引。這不廢話嗎，當然得和 put的時候一樣了，不一樣還怎麼找到正確的位置。

確定桶的位置后，會出現三種情況：

單節點類型： 也就是這個桶內只有一個鍵值對，這也在 HashMap中存在最多的類型，只要不發生哈希碰撞都是這種類型。其實 HashMap最理想的情況就是這樣，全都是這種類型就完美了。

鏈表類型： 如果發現 get 的 key 所在的是一個鏈表結構，就需要遍歷鏈表，知道找到 key 相等的 Node。

紅黑樹類型： 當鏈表長度超過 8 就轉變成紅黑樹，如果發現找到的桶是一顆紅黑樹，就使用紅黑樹專有的快速查找法查找。

另外，Map.containsKey方法其實用的就是 get方法。

remove 方法

remove與put、get方法類似，都是先求出 key 的 hash 值，然後 (n-1) & hash獲取索引位置，之後根據節點的類型採取不同的措施。

單節點類型： 直接將當前桶元素替換為被刪除 node.next ，其實就是 null。

鏈表類型： 如果是鏈表類型，就將被刪除 node 的前一個節點的 next 屬性設置為 node.next。

紅黑樹類型： 如果是一棵紅黑樹，就調用紅黑樹節點刪除法，這裏，如果節點數在 2~6之間，就將樹結構簡化為鏈表結構。

非線程安全

HashMap沒有做併發控制，如果想在多線程高併發環境下使用，請用 ConcurrentHashMap。同一時刻如果有多個線程同時執行 put 操作，如果計算出來的索引（桶）位置是相同的，那會造成前一個 key 被后一個 key 覆蓋。

比如下圖線程 A 和 線程 B 同時執行 put 操作，很巧的是計算出的索引都是 2，而此時，線程A 和 線程B都判斷出索引為 2 的桶是空的，然後就是插入值了，線程A先 put 進去了 key1 = 1的鍵值對，但是，緊接着線程B 又 put 進去了 key2 = 2，線程A 表示痛哭流涕，白忙活一場。最後索引為2的桶內的值是 key2=2，也就是線程A的存進去的值被覆蓋了。

總結

前面沒說，HashMap搞的這麼複雜不是白搞的，它的最大優點就是快，尤其是 get數據，是 O(1)級別的，直接定位索引位置。

HashMap不是單純的數組結構，當發生哈希碰撞時，會採用拉鏈法生成鏈表，當鏈表大於 8 的時候會轉換成紅黑樹，紅黑樹可以很大程度上提高性能。

HashMap容量必須是 2 的 n 次方，這樣設計是為了保證尋找索引的散列計算更加均勻，計算索引的公式為 (n - 1) & hash。

HashMap在鍵值對數量達到擴容閾值「容量 x 負載因子」的時候進行擴容，每次擴容為之前的兩倍。擴容的過程中會對單節點類型元素進行重新計算索引位置，如果是紅黑樹節點則使用 split方法重新考量，是否將紅黑樹變為鏈表。

壯士且慢，先給點個贊吧，總是被白嫖，身體吃不消！

我是風箏，公眾號「古時的風箏」。一個兼具深度與廣度的程序員鼓勵師，一個本打算寫詩卻寫起了代碼的田園碼農！你可選擇現在就關注我，或者看看歷史文章再關注也不遲。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※超省錢租車方案

※別再煩惱如何寫文案,掌握八大原則!

※回頭車貨運收費標準

※教你寫出一流的銷售文案?

※FB行銷專家,教你從零開始的技巧