transient Node<K,V>[] table; // 桶數(shù)組
transient int size; // 統(tǒng)計(jì) HashMap 實(shí)例中有多少個(gè)元素，不等于 table.length

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

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

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

  static final int tableSizeFor(int cap) {
    int n = cap - 1; // 處理特殊情況：cap 恰好為 2 的 n 次方，即最高二進(jìn)制位 1 右邊全部為 0 的情況
    n |= n >>> 1; // 最二進(jìn)制位1右邊1位填充 1 個(gè) 1
    n |= n >>> 2; // 繼續(xù)填充2個(gè) 1
    n |= n >>> 4; // 填充 4 個(gè) 1
    n |= n >>> 8; // 填充 8 個(gè) 1
    n |= n >>> 16; //填充 16 個(gè) 1。 執(zhí)行完這句之后，已經(jīng)確保最高位右邊部分全部填充成了 1，例如：cap = 101_0101b 時(shí)，n = 111_1111b
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; // n+1 進(jìn)位，返回 1000_0000b
  }

  // 傳入 initialCapacity，負(fù)載因子使用的是默認(rèn)值 0.75
  public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
  }
  // capacity 和 loadFactor 均使用默認(rèn)值
  public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
  }

  // 傳入一個(gè) map，傳入的元素會(huì)逐個(gè)放入到新構(gòu)造的 HashMap 實(shí)例中
  public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
  }

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

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
        boolean evict) {
  // tab 代表 table 數(shù)組；p 表示節(jié)點(diǎn)；n 表示桶的數(shù)量；i 指向應(yīng)該放入的桶的下標(biāo)
  Node<K,V>[] tab; Node<K,V> p; int n, i;
  // table 沒有初始化，調(diào)用 resize() 構(gòu)造 table 數(shù)組
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  // 如果桶中沒有元素，則 table 數(shù)組的元素作為節(jié)點(diǎn)
  if ((p = tab[i = (n - 1) & hash]) == null) // 因?yàn)?n=2^x，所以 (n-1)&hash 等價(jià)于 hash % n
    tab[i] = newNode(hash, key, value, null);
  else { // 桶中有元素
    Node<K,V> e; K k; // e 表示要存放值的 Node ， k 表示對(duì)應(yīng)的鍵，如果鍵不存在 e 的值為空，如果鍵存在，讓 e 指向該節(jié)點(diǎn)
    if (p.hash == hash && // p 此時(shí)指向 table 中的元素，也就是鏈表或者樹的根
      ((k = p.key) == key || (key != null && key.equals(k)))) // 如果 p.key 恰好與 key 相等，存在著一個(gè)節(jié)點(diǎn)，讓 e 指向它
      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);
          // 這一句很魔幻，有人說鏈表中達(dá)到了 7 個(gè)元素就會(huì)被樹化，也有說是 8 個(gè)的，
          // 實(shí)際上往桶里放入第 9 個(gè)元素時(shí)才會(huì)樹化，不信可以看一下這個(gè)實(shí)驗(yàn)：https://github.com/Robothy/java-experiments/blob/main/HashMap/TreeifyThreshold/TreeifyThresholdTest.java
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
          break;
        }
        if (e.hash == hash &&
          ((k = e.key) == key || (key != null && key.equals(k)))) // 在鏈表中找到了相同的 key
          break;
        p = e;
      }
    }
    // 如果 key 已經(jīng)存在了，HashMap 不會(huì)取構(gòu)造新的 Node，而是直接修改 Node 中的 value 屬性
    if (e != null) { // existing mapping for key
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      afterNodeAccess(e); // 這句在這里什么也沒干，留給 LinkedHashMap 的
      return oldValue;
    }
  }
  ++modCount; // 操作數(shù)統(tǒng)計(jì)，用來檢查是否有多個(gè)線程同時(shí)修改 HashMap，JDK中很多非線程安全的容器中都用了這些操作
  if (++size > threshold) // size 超過了 threshold，進(jìn)行擴(kuò)容操作
    resize();
  afterNodeInsertion(evict);
  return null;
}

final Node<K,V>[] resize() {
  Node<K,V>[] oldTab = table; // oldTab 指向舊的 table
  int oldCap = (oldTab == null) ? 0 : oldTab.length; // 舊table的長(zhǎng)度，如果 table 為空，則長(zhǎng)度為 0
  int oldThr = threshold; // 舊的閾值，如果 table 沒有初始化，threshold 臨時(shí)存儲(chǔ)的是構(gòu)造方法中根據(jù) initialCapacity 計(jì)算的初始 capacity
  int newCap, newThr = 0;
  if (oldCap > 0) { // 這句的含義是 table 已經(jīng)初始化了，現(xiàn)在要對(duì)它擴(kuò)容
    if (oldCap >= MAXIMUM_CAPACITY) { // 值已經(jīng)達(dá)到了 2^31，不能再擴(kuò)容了，因?yàn)?int 范圍內(nèi)不能再進(jìn)行乘以 2 操作了，否則會(huì)導(dǎo)致整數(shù)溢出
      threshold = Integer.MAX_VALUE; // 直接將 threshold 的值提高到 int 范圍內(nèi)的最大值，讓后續(xù)的 put 操作不再觸發(fā) resize()
      return oldTab; // 直接返回，不擴(kuò)容了
    }
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
         oldCap >= DEFAULT_INITIAL_CAPACITY)
      newThr = oldThr << 1; // 新的 threshold 變?yōu)樵瓉淼膬杀?，因?yàn)樾碌?capacity 也是原來的兩倍，而 threshod = capacity * loadFactor 
  }
  else if (oldThr > 0) // 舊的 threshold 大于 0；含義是 table 需要初始化，不過在構(gòu)造 HashMap 時(shí)指定了 initialCapacity，table 的初始長(zhǎng)度已經(jīng)定下來了，臨時(shí)存放在 this.threshold 中，等于 oldThr
    newCap = oldThr; // 那么新的 table 的長(zhǎng)度直接設(shè)置為 oldThr 即可
  else { // 含義是 table 需要初始化，但是構(gòu)造器中沒有指定初始化的相關(guān)參數(shù)，則直接使用默認(rèn)參數(shù)計(jì)算即可
    newCap = DEFAULT_INITIAL_CAPACITY; // 值為 16
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 值為 16 * 0.75 = 12
  }
  if (newThr == 0) { // table 需要初始化，且構(gòu)造器中指定了初始化參數(shù)
    float ft = (float)newCap * loadFactor; // 使用構(gòu)造器指定的參數(shù)計(jì)算閾值，臨時(shí)放在 ft 中。新閾值 = 新數(shù)組長(zhǎng)度 * 負(fù)載因子
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
         (int)ft : Integer.MAX_VALUE); // 檢查 ft 有沒有超出范圍，畢竟是用戶輸入的參數(shù)，需要進(jìn)行檢查
  }
  threshold = newThr; // 將前面步驟中計(jì)算得到的 newThr 賦值給 this.threshold
  @SuppressWarnings({"rawtypes","unchecked"})
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 實(shí)例化新的 Node 數(shù)組
  table = newTab; // 讓 table 指向新的 Node 數(shù)組
  if (oldTab != null) { // 舊的 table 不為空，則需要將舊 table 中的元素放到新的 table 中
    // 省略將舊的 table 中的元素放到新的 table 中的代碼
  }
  return newTab;
}

if (oldTab != null) {
  for (int j = 0; j < oldCap; ++j) { // 逐個(gè)遍歷桶
    Node<K,V> e;
    if ((e = oldTab[j]) != null) { // 桶中有元素
      oldTab[j] = null;
      if (e.next == null) // 桶中只有1個(gè)元素
        newTab[e.hash & (newCap - 1)] = e;
      else if (e instanceof TreeNode) // 桶為紅黑樹
        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 同樣拆分成兩個(gè)桶
      else { // 桶為單鏈表
        Node<K,V> loHead = null, loTail = null; // 子鏈表（新桶），存放哈希值 % newCap == j 的元素
        Node<K,V> hiHead = null, hiTail = null; // 子鏈表（新桶），存放哈希值 % newCap == j + oldCap 的元素。
        
        Node<K,V> next;
        do { // 遍歷鏈表
          next = e.next;
          if ((e.hash & oldCap) == 0) { // 算法比較巧妙，通過臨界的 1 位二進(jìn)制位即可判斷該哈希值余上 newCap 所屬桶
            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) { // 余數(shù)較小的桶有元素
          loTail.next = null;
          newTab[j] = loHead;
        }
        if (hiTail != null) { // 余數(shù)較大的桶有元素
          hiTail.next = null;
          newTab[j + oldCap] = hiHead;
        }
      }
    }
  }
}

public V get(Object key) {
  Node<K,V> e;
	// 計(jì)算哈希值
  return (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> first, e; int n; K k;
  if ((tab = table) != null && (n = tab.length) > 0 &&
    (first = tab[(n - 1) & hash]) != null) { // hash%table.length 定位到桶
		
    if (first.hash == hash && // always check first node
      ((k = first.key) == key || (key != null && key.equals(k))))
      return first; // 直接取 table 中的元素
    if ((e = first.next) != null) {
      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);
    }
  }
  return null;
}

public V remove(Object key) {
  Node<K,V> e;
  return (e = removeNode(hash(key), key, null, false, true)) == null ?
    null : e.value;
}

public boolean remove(Object key, Object value) {
  return removeNode(hash(key), key, value, true, true) != null;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
              boolean matchValue, boolean movable) {
  Node<K,V>[] tab; Node<K,V> p; int n, index;
  if ((tab = table) != null && (n = tab.length) > 0 &&
    (p = tab[index = (n - 1) & hash]) != null) {
    Node<K,V> node = null, e; K k; V v;
    if (p.hash == hash &&
      ((k = p.key) == key || (key != null && key.equals(k)))) // key 為桶中的第 1 個(gè)元素
      node = p; // 直接取 table[(n-1)&hash] 
    else if ((e = p.next) != null) { // 桶中超過 1 個(gè)元素
      if (p instanceof TreeNode) // 桶為紅黑樹
        node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
      else { // 桶為單鏈表
        do { // 單鏈表搜索
          if (e.hash == hash &&
            ((k = e.key) == key ||
             (key != null && key.equals(k)))) {
            node = e;
            break;
          }
          p = e;
        } while ((e = e.next) != null);
      }
    }
		
		// 若找到了 key，對(duì)應(yīng)的節(jié)點(diǎn)由 node 指向
    if (node != null && (!matchValue || (v = node.value) == value ||
               (value != null && value.equals(v)))) { // 檢查 key 和 value 是否均符合要求
      if (node instanceof TreeNode) // node 為紅黑樹節(jié)點(diǎn)
        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); // 執(zhí)行紅黑樹移除操作
      else if (node == p) // 查找到的 node 為桶中的第 1 個(gè)元素
        tab[index] = node.next; 
      else
        p.next = node.next; // 執(zhí)行單鏈表移除
      ++modCount;
      --size;
      afterNodeRemoval(node);
      return node;
    }
  }
  return null;
}

public Set<Map.Entry<K,V>> entrySet() {
  Set<Map.Entry<K,V>> es;
  return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

int index;       // 指向當(dāng)前的桶，初始值為 0
final Node<K,V> nextNode() {
  Node<K,V>[] t;
  Node<K,V> e = next;
  if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
  if (e == null)
    throw new NoSuchElementException();
  if ((next = (current = e).next) == null && (t = table) != null) {
    do {} while (index < t.length && (next = t[index++]) == null); // 不斷地跳過空的桶
  }
  return e;
}