HashMap 源码精讲：数组+链表+红黑树

// 默认初始容量 = 16（1 << 4），必须是 2 的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

// 最大容量 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认负载因子 0.75（时间与空间的折中）
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 链表转红黑树的阈值：链表长度 ≥ 8
static final int TREEIFY_THRESHOLD = 8;

// 红黑树退化回链表的阈值：节点数 ≤ 6
static final int UNTREEIFY_THRESHOLD = 6;

// 树化的另一前提：数组长度必须 ≥ 64，否则优先扩容
static final int MIN_TREEIFY_CAPACITY = 64;

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;   // 缓存的 hash 值，避免重复计算
    final K key;     // key 用 final 修饰 —— 这也是不能改 key 的原因
    V value;
    Node<K,V> next;   // 指向同一个桶里的下一个节点

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

static final int hash(Object key) {
    int h;
    // key 为 null 时 hash = 0 —— 这就是 HashMap 允许 null key 的原因，
    // 且 null key 永远落在 0 号桶
    return (key == null) ? 0
         : (h = key.hashCode()) ^ (h >>> 16);
    //       ↑ 取原始 hashCode      ↑ 高 16 位无符号右移后异或
}

// n 是数组长度，tab 是 table 数组
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
// (n-1) & hash 等价于 hash % n，但位运算比取模快得多

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;

    // ① table 为空 → 触发 resize() 初始化
    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 {
        Node<K,V> e; K k;
        // ④ 桶第一个节点 key 就相同 → 记下，待会儿覆盖
        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)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;  // 链表中找到相同 key
                p = e;
            }
        }
        // 找到了相同 key 的节点 → 覆盖 value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            return oldValue;   // 返回旧值
        }
    }
    ++modCount;
    // ⑧ size 超过阈值 → 扩容
    if (++size > threshold)
        resize();
    return null;   // 新增 key，返回 null
}

// loHead/loTail：低位链表（留在原索引 j）
// hiHead/hiTail：高位链表（移到索引 j + oldCap）
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
    next = e.next;
    // 关键：用 hash & oldCap 判断新增的那一位是 0 还是 1
    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);

// 低位链表：原位 j
if (loTail != null) { loTail.next = null; newTab[j] = loHead; }
// 高位链表：新位 j + oldCap
if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }