HashMap原理學會了嗎？（HashMap存儲及擴容）

目錄

• debug熟悉HashMap的源碼
• • 1、建立HashMap，添加第一個資料時
  • • （1）執行`new HashMap<>();`
    • （2）執行`map.put(key,value);`方法
  • 2、添加後續資料
  • • (1) 添加完資料之後，`map.size`小于門檻值
    • • <1> 未發生hash沖突時,直接添加成功
      • <2> 發生hash沖突時
    • (2) 添加完資料之後，`map.size`大于門檻值
    • • <2> 當容器存儲資料量達到門檻值時
  • 3、關于樹化和樹化節點的擴容

debug熟悉HashMap的源碼

1、建立HashMap，添加第一個資料時

（1）執行

new HashMap<>();

• 調用構造器，設定負載因子為預設負載因子（0.75）：

  static final float DEFAULT_LOAD_FACTOR = 0.75f;

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

（2）執行

map.put(key,value);

方法

• put()

  方法調用

  putVal()

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
           

• 計算hash：
  • 如果

    key

    為

    null

    ，則設定

    key

    的 hash = 0
  • 如果不為

    null

    ，則調用

    String.hashCode()

    方法計算hash值（

    Object.hashCode()

    —>

    String.hashCode()

    ）

  public int hashCode() {
      int h = hash;
      if (h == 0 && value.length > 0) {
          char val[] = value;
  
          for (int i = 0; i < value.length; i++) {
              h = 31 * h + val[i];
          }
          hash = h;
      }
      return h;
  }	
             

  • 然後将計算得到的hash和無符号右移16位之後的hash進行異或（

    ^

    ）運算，再和本身異或，得到最後的hash值

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

• 執行

  putVal()

  • 首先會判斷是不是建立的

    HashMap

    ，如果是，此時會調用

    resize()

    初始化

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

  • resize()

    使用到的部分：

    • transient Node<K,V>[] table;

      這裡面的table就是

      HashMap

      存儲資料的容器
    • 預設容量：

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

    • 負載因子：

      static final float DEFAULT_LOAD_FACTOR = 0.75f;

    • newThr

      ：初始化獲得的門檻值為12

  //resize()
  else {               // zero initial threshold signifies using defaults
      newCap = DEFAULT_INITIAL_CAPACITY;
      newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  
  threshold = newThr;
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  table = newTab;
  //因為newTab為null，傳回newTab
  return newTab;
             

  • 初始化存儲容器之後，會計算資料的存儲位置：

    (n - 1) & hash

    ,并判斷該位置上是否已經有元素
    • 我們是第一次添加，此時是沒有元素的，是以直接将元素放在該位置上

    //putVal()
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    /*
    	Node是HashMap上存儲資料的節點
        // Create a regular (non-tree) node
        Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
            return new Node<>(hash, key, value, next);
        }
    */
               

  • 然後給統計修改次數（hash計算次數）的計數器自增1：

    ++modCount;

• putVal()

  結束，

  put()

  結束，存儲完成

2、添加後續資料

(1) 添加完資料之後，

map.size

小于門檻值

<1> 未發生hash沖突時,直接添加成功

//putVal()
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
           

<2> 發生hash沖突時

• 會判斷是否已經有相同的

  key

  ,如果相同會把之前的

  Node

  節點覆寫

//p = tab[i = (n - 1) & hash]
Node<K,V> e; K k;
if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;

if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}
           

• 然後會判斷是否為樹節點，如果是，則将值存在紅黑樹中

else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
           

• 如果都不是，則将新的

  Node

  挂到該位置上的節點之後

else {
    for (int binCount = 0; ; ++binCount) {
        //判斷目前位置的節點是否有子節點
        if ((e = p.next) == null) {
            //如果沒有子節點，則在将新節點挂在p->next上
            p.next = newNode(hash, key, value, null);
            //判斷是否大于樹化的門檻值，如果大于則進行樹化操作
            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;
        //如果目前有子節點，則通過循環将新節點挂在子節點的next上
        p = e;
    }
}
           

(2) 添加完資料之後，

map.size

大于門檻值

<2> 當容器存儲資料量達到門檻值時

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

• 調用

  resize()

  擴容
  • 如果目前容量達到預設的最大容量，則将門檻值調到Integer類型的最大值，不改變最大容量

    if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
    }
               

  • 如果沒有達到最大容量，則将容量按位右移一位（擴大2倍），并将門檻值按位右移一位（擴大2倍）

    else if ( (newCap = oldCap << 1) < MAXIMUM_CAPACITY 
              && oldCap >= DEFAULT_INITIAL_CAPACITY)
         newThr = oldThr << 1; // double threshold
               

  • 擴容完成後，先将資料拷貝，然後再将拷貝的資料遷移到新數組的相應位置（遷移過程中一個很巧妙的算法：

    (e.hash & oldCap) == 0

    ，當為0時，資料節點不需要移動位置，不為0 時，則将節點向後移動一個舊容量的長度的位置，具體算法了解起來有些複雜，建議百度看大佬的分析）
  • 遷移過程中判斷是否有子節點，是否為樹的根節點
    • 如果有子節點，且轉化為紅黑樹，則通過

      ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

      來完成資料的遷移
    • 如果有子節點，且子節點沒有轉化為紅黑樹，則執行以下操作：
      • 定義的兩中含義不同的

        Node

        ：

        lo

        和

        hi

        ，

        lo

        節點是放到原位置，

        hi

        節點是放到偏移之後的位置

        Node<K,V> loHead = null, loTail = null;
        Node<K,V> hiHead = null, hiTail = null;
                   

      • 資料拷貝（拿一種情況來分析，因為存儲位置是否偏移對資料拷貝無影響）

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

• 以上步驟會執行舊容量大小的次數來将所有資料遷移到數組中，遷移完成之後将新的數組傳回

3、關于樹化和樹化節點的擴容

紅黑樹部分内容暫時還未深入學習，涉及到紅黑樹這個資料結構，等深入學習到紅黑樹原理時再深挖這一塊

treeifyBin(tab, hash);	//樹化
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);	//擴容