概括

HashMap是關聯數組、哈希表和紅黑樹的集合。線程不安全。允許空鍵和空值。這是不正常的。

底層數據結構是一個數組，稱為哈希表。每個位置都有一個鏈表。鏈表中的每個節點都是 HashMap 中的每個元素。

如果鏈表的元素個數大于等于8，則鏈表會轉化為紅黑樹，以提高查詢效率。

HashMap的結構如下：

下圖是HashMap繼承和實現的接口

基本數據結構

桶陣列

一個數組，每個位置后跟一個鏈表。

瞬態節點<K,V>[] 表；

鏈表節點

靜止的
  class Node<K,V> 實現 Map.Entry<K,V> {
  最終的整數哈希；// 哈希值
  最終K鍵；
  V值；
  下一個節點<K,V>；// 鏈表中的下一個節點
// 構造函數
  Node(int hash, K key, V value, Node<K,V> next) {
    this.hash = 哈希；
    this.key = 鍵；
    this.value = 值；
    this.next = 下一個；
  }
  public final K getKey() { 返回鍵；}
  公共最終 V getValue() { 返回值；}
  public final String toString() { return key + "=" + value; }
// 節點的hashCode是通過key和value的hashCode異或得到的。
  公共最終 int hashCode() {
    返回 Objects.hashCode(key) ^ Objects.hashCode(value);
  }
// 設置新值并返回舊值
  公共最終 V setValue(V newValue) {
    V oldValue = 值；
    值 = 新值；
    返回舊值；
  }
// 判斷是否為節點。
  公共最終布爾等于（對象 o）{
    如果（o == 這個）
      返回真；
    if (o instanceof Map.Entry) {
      Map.Entry<?,?> e = (Map.Entry<?,?>)o;
      if (Objects.equals(key, e.getKey()) &&
          Objects.equals(value, e.getValue()))
        返回真；
    }
    返回假；
  }
}

紅黑樹

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
  TreeNode<K,V> parent;  // Father node
  TreeNode<K,V> left;			// Left son
  TreeNode<K,V> right;		// Right son
  TreeNode<K,V> prev;    // needed to unlink next upon deletion
  boolean red; 					// colour
  TreeNode(int hash, K key, V val, Node<K,V> next) {
    super(hash, key, val, next);
  }
// Return to root node
  final TreeNode<K,V> root() {
    for (TreeNode<K,V> r = this, p;;) {
      if ((p = r.parent) == null)
        return r;
      r = p;
    }
  }
}

基本要素

在查看源代碼之前，您需要了解一些常量的含義。只是有印象。

負載系數

總容量 * 負載系數 = 閾值

如果地圖中的元素數量大于閾值，則需要對其進行擴展。

如果填充比例很大，則意味著使用了大量空間。如果不是一直進行擴展，鏈表會越來越長，所以搜索的效率很低，因為鏈表的長度很大(紅黑后會提升很多)樹在最新版本中使用)。擴展后，原鏈表數組的每個鏈表會被分成兩個子鏈表，掛在新鏈表數組的hash位置，這樣每個鏈表的長度減少，查找效率高增加

// 默認初始容量為 16。容量的大小必須是 2 的幾個冪。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 
// 最大容量不應超過 1 < 30 
static final int MAXIMUM_CAPACITY = 1 << 30; 
// 負載因子為 0.75 
static final float DEFAULT_LOAD_FACTOR = 0.75f; 
// 樹的閾值。單個鏈表中的元素數。鏈表向紅黑樹轉換的判斷條件。
靜態最終 int TREEIFY_THRESHOLD = 8; 
// 樹退化的閾值。單個鏈表中的元素數。紅黑樹退化的判斷條件
static final int UNTREEIFY_THRESHOLD = 6;
// 最小樹容量。這是指地圖中元素的總數。
靜態最終 int MIN_TREEIFY_CAPACITY = 64; 
// ---------------------------------------------- 
//每個位置有幾個元素的哈希表。
瞬態節點<K,V>[] 表；
瞬態集<Map.Entry<K,V>> entrySet; 
// 一個map中的元素個數
transient int size; 
// 修改次數
瞬態 int modCount; 
// 擴容閾值。如果超過閾值，將擴大容量。（容量 * 負載因子）
int 閾值；
// 哈希表的加載因子
final float loadFactor;

構造函數

有四種類型的構造函數。詳情請參考以下代碼注釋。

// 給定初始容量，負載因子
public HashMap(int initialCapacity, float loadFactor) { 
  if (initialCapacity < 0) 
    throw new IllegalArgumentException("Illegal initial capacity: " +                                        initialCapacity); 
  如果（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); 
} 
// 給定初始容量
public HashMap(int initialCapacity) {
  // 調用上面的構造函數，給定容量和負載因子
  this(initialCapacity, DEFAULT_LOAD_FACTOR); 
} 
// 默認
public HashMap() { 
  this.loadFactor = DEFAULT_LOAD_FACTOR; // 所有其他字段默認
} 
// 從現有地圖創建一個新地圖。
public HashMap(Map<? extends K, ? extends V> m) { 
  this.loadFactor = DEFAULT_LOAD_FACTOR; 
  putMapEntries(m, false); 
}

構造函數調用以下代碼塊。

// 返回大于或等于 cap 的最小值 2 的冪數。
靜態最終 int tableSizeFor(int cap) { 
  int n = cap - 1; 
  // 即把二進制最高位1后的位置全部改為1 
  n |= n >>> 1; 
  n |= n >>> 2; 
  n |= n >>> 4; 
  n |= n >>> 8; 
  n |= n >>> 16; 
	// 與最大容量相比，不能超過最大容量。
  返回 (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ？最大容量：n + 1；
} 
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { 
  int s = m.size(); 
  if (s > 0) { 
    if (table == null) { // 預大小
      // 計算閾值的大小。
      float ft = ((float)s / loadFactor) + 1.0F; 
      // 與最大容量相比，如果超過最大容量，則成為最大容量。
      int t = ((ft < (float)MAXIMUM_CAPACITY) ? 
               (int)ft : MAXIMUM_CAPACITY); 
      if (t > threshold) 
        // 將閾值重新計算為 2 的冪。
        threshold = tableSizeFor(t); 
    } 
    else if (s > threshold) 
      // 如果現有集合元素個數大于閾值，則需要進行擴展。
      調整大小（）；
    // 遍歷集合，一一加入當前集合。
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { 
      K key = e.getKey(); 
      V 值 = e.getValue(); 
      putVal(hash(key), key, value, false, evict); 
    } 
  } 
}

HashMap的訪問和擴展

擴張

HashMap 的默認容量為 16，擴展時調整為原來的兩倍。所以容量必須是 2 的某個冪。

final Node<K,V>[] resize() { 
  Node<K,V>[] oldTab = table; 
  // 獲取地圖的大小。
  int oldCap = (oldTab == null) ? 0 : oldTab.length; 
  // 當前閾值
  int oldThr = threshold; 
  int newCap，newThr = 0；
  // 當前容量大于0 
  if (oldCap > 0) { 
    // 當前容量已達到上限
    if (oldCap >= MAXIMUM_CAPACITY) { 
      // 閾值設置為2 ^ 31-1 
      threshold = Integer. MAX_VALUE; 
      // 返回當前哈希表，不擴展
      return oldTab; 
    }
    // 新容量擴大到舊容量的兩倍，新容量小于最大容量，舊容量大于等于16 
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 
             oldCap >= DEFAULT_INITIAL_CAPACITY) 
      newThr = oldThr << 1; // 閾值加倍
  } // 如果當前表為空但有閾值。表示初始化時指定了容量和閾值的情況
  else if (oldThr > 0) // 如果有舊閾值，則新容量等于舊閾值，舊閾值是2的幾個冪
    newCap = oldThr; 
  else { // 默認情況下，如果沒有容量或閾值，則設置默認容量和閾值
    newCap = DEFAULT_INITIAL_CAPACITY; 
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 
  } 
  if (newThr == 0) { // 如果新閾值為0，重新計算閾值。
    float ft = (float)newCap * loadFactor; 
    // 防止越過閾值
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 
              (int)ft : Integer.MAX_VALUE); 
  } 
  // 更新閾
  值 threshold = newThr; 
  @SuppressWarnings({"rawtypes","unchecked"}) 
  // 根據新增容量，新建哈希表
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap ]; 
  // 更新引用
  table = newTab;
  // 如果舊表不為空
  if (oldTab != null) { 
    // 循環遍歷舊哈希表的每個位置。
    for (int j = 0; j < oldCap; ++j) { 
      // 臨時節點 e 
      Node<K,V> e; 
      // 臨時節點引用當前位置。
      if ((e = oldTab[j]) != null) { 
        // GC 
        oldTab[j] = null;將舊哈希表的位置設置為null; 
        // 如果當前位置只有一個元素，則將其插入到新表中，
        // e. Hash & (newcap - 1) 這是計算當前節點在哪里
        if (e.next == null) 
          newTab[e.hash & (newCap - 1)] = e;
        // 如果是紅黑樹，按照紅黑樹的方法將當前位置的節點分開
        else if (e instanceof TreeNode) 
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 
        else { // 保留順序
          // 低序列表的頭尾，0 ～ oldcap - 1 
          Node<K,V> loHead = null, loTail = null; 
          // 高階鏈表的頭尾 oldCap ～ newCap - 1 
          Node<K,V> hiHead = null, hiTail = null; 
          // 臨時變量
          Node<K,V> next; 
          做 {
            下一個 = e.next;
            // 判斷二進制的最高位是0還是1，如果是0，則將節點放入低位鏈表，否則為高位鏈表。
            if ((e.hash & oldCap) == 0) { 
              if (loTail == null) 
                loHead = e; 
              否則
                loTail.next = e; 
              loTail = e; 
            } // 二進制最高位為1，節點放入高階鏈表
            else { 
              if (hiTail == null) 
                hiHead = e; 
              否則
                hiTail.next = e; 
              hiTail = e; 
            } 
          } while ((e = next) != null);
          // 下面的列表放在j的位置，
          if (loTail != null) { 
            loTail.next = null; 
            newTab[j] = loHead; 
          } 
          // 高階列表放在j+oldCap的位置。
          if (hiTail != null) { 
            hiTail.next = null; 
            newTab[j + oldCap] = hiHead; 
          } 
        } 
      } 
    } 
  }
  返回 newTab; 
}

如果當前容量大于0且當前容量達到上限，則不擴容直接返回。沒有達到上限，擴大到原來的兩倍。

如果當前容量為0，則將容量和閾值設置為默認值。

對舊表中的元素進行分類，計算每個key的hash值，判斷key是在(原位置)還是(原位置+舊容量)

放置值

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) { 
  // tab存儲當前哈希表，p為臨時變量。
  節點<K,V>[] 選項卡；節點<K,V> p; 國際n，我；
  // 如果哈希表為空，則應先對其進行擴展。
  if ((tab = table) == null || (n = tab.length) == 0) 
    n = (tab = resize()).length;   
  // 計算哈希表中的位置。如果倉位為空，則不會有哈希沖突。只需創建一個新節點。
  // 查找哈希表中的位置，使用位操作來加快運算速度。
  if ((p = tab[i = (n - 1) & hash]) == null) 
    tab[i] = newNode(hash, key, value, null); 
  else { 
    // e 是一個臨時變量。如果它不為空，則意味著該值應該像鍵一樣被覆蓋。
    節點<K,V> e; Ｋ；
    // hash相同，找到位置，key相同，覆蓋。e 記錄要覆蓋的位置。
    if (p.hash == hash && 
        ((k = p.key) == key || (key != null && key.equals(k)))) 
      e = p; 
    // 紅黑樹的情況。
    else if (p instanceof TreeNode) 
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 
    else { 
      // 遍歷列表，插入值
      for (int binCount = 0; ; ++binCount) { 
        // 如果到達列表的末尾，只需添加值。
        if ((e = p.next) == null) { 
          p.next = newNode(hash, key, value, null); 
          // 如果添加的節點數> = 8，則轉化為紅黑樹。
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 表示第一個
            treeifyBin(tab, hash); 
          休息; 
        } 
        // 在遍歷的過程中，key是一樣的，tocover，e就是要覆蓋的位置，直接break。
        if (e.hash == hash && 
            ((k = e.key) == key || (key != null && key.equals(k))))
          中斷；
        p = e; 
      }
    } 
    // 有需要覆蓋的位置。
    if (e != null) { // 鍵
      V 的現有映射oldValue = e.value; 
      if (!onlyIfAbsent || oldValue == null) 
        e.value = value; 
      afterNodeAccess(e); 
      返回舊值；
    } 
  } 
  ++ modCount的; 
  // 如果元素個數大于閾值，則擴容
  if (++size > threshold) 
    resize(); 
  afterNodeInsertion（驅逐）；
  返回空；
}

1.判斷數組table[i]的鍵值對是否為空或null，否則執行resize()展開;

2.根據鍵值key，對插入的數組索引I計算hash值，如果table[i]==null，直接新建節點并添加。轉6，如果table[i]不為空，轉3;

3.判斷table[i]的第一個元素是否與key相同。如果相同，則直接覆蓋值。否則轉4。這里相同指的是hashCode和equals;

4.判斷table[i]是否為treeNode，即table[i]是否為紅黑樹。如果是紅黑樹，直接在樹中插入鍵值對，否則轉⑤;

5.遍歷table[i]判斷鏈表添加元素后的長度是否大于等于8，如果大于等于8，則將鏈表轉化為紅黑樹，并執行in中的插入操作紅黑樹。否則，插入鏈表。如果遍歷過程中key已經存在，直接覆蓋value;

6.插入成功后，判斷實際key value對數量size是否超過最大容量閾值。如果超過，請擴大容量。

獲取值

public V get(Object key) { 
  Node<K,V> e; 
  返回 (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> 首先，e；國際n; Ｋ；
  // 哈希表中有內容，然后在哈希表中找到key的位置。
  if ((tab = table) != null && (n = tab.length) > 0 && 
      (first = tab[(n - 1) & hash]) != null) { 
    // 總是判斷第一個節點是否是一個要找到。如果是，則返回
    if (first.hash == hash && // 始終檢查第一個節點
        ((k = first.key) == key || (key != null && key.equals(k)))) 
      return first;    
      // 如果是紅黑樹，則轉到紅黑樹
      if (first instanceof TreeNode) 
        return ((TreeNode<K,V>)first).getTreeNode(hash, key); 
      do { 
        // 查看鏈表
        if (e.hash == hash && 
            ((k = e.key) == key || (key != null && key.equals(k)))) 
          return e; 
      } while ((e = e.next) != null); 
    } 
  }
  返回空值；
}

Map中有內容。根據key的hash值，找到key所在的索引。

查找索引，判斷第一個節點是否是要查找的節點，如果是則返回。

判斷下面的節點是否是紅黑樹。如果是這樣，去紅黑樹。

不是紅黑樹，遍歷鏈表尋找。

如果未找到則返回 null

以上就是關于“應該知道的HashMap源碼分析”的介紹，大家如果想了解更多相關知識，不妨來關注一下動力節點的Java基礎教程，里面的課程內容豐富，由淺到深，通俗易懂，很適合沒有基礎的小伙伴學習，希望對大家能夠有所幫助。