這些年，被面試官問到的HashMap

前言

HashMap 是無論在作業還是面試中都非常常見常考的資料結構，

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

這里我也整理了一些最近群友去面試整理的面試資料，提供大家參考！還是感謝群友的開源精神！

有需要的小伙伴可以點擊進入暗號：csdn，免費獲取，還有更多Java專題檔案筆記，

如果這篇文章你覺得還不錯，記得點贊哦，有任何不妥的地方還請不吝指教！

先從結構說起

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

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

先來看一下整個 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最核心的原理，主要包括以下幾點：

• 什么情況下會擴容，擴容的規則是什么？
• 插入鍵值對的時候如何確定索引，HashMap可不是按順序插入的，那樣不就真成了陣列了嗎，
• 如何確保 key 的唯一性？
• 發生哈希碰撞怎么處理？
• 拉鏈法是什么？
• 單桶內的鏈表如何轉變成紅黑樹？
  以下是 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 中沒有真正的動態陣列這一說，陣列初始化的時候是多大，那它就一直是這么大，那擴容是怎么來的呢，答案就是創建一個新陣列，然后將老陣列的資料拷貝過去，

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

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

確定插入點

當我們呼叫 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方法重新考量，是否將紅黑樹變為鏈表，