HashMap 源码分析

本文为Java 基础系列 - HashMap 源码分析先讲 HashMap ，所依赖的树结构（二叉搜索树、AVL、红黑树），再讲 HashMap 的数组+链表+红黑树实现与关键源码，文中配有树形/结构图。

一、二叉搜索树（BST）

1.1 定义与性质

二叉搜索树：每个结点左子树上所有结点值 < 根，右子树上所有结点值 > 根；中序遍历得到有序序列。
查找、插入、删除：理想情况 O(log n)，退化成链时 O(n)。

1.2 二叉搜索树示例（结构图）

以下为一棵关键字为 5, 3, 7, 1, 4 的 BST：

flowchart TB
    subgraph BST["二叉搜索树"]
        direction TB
        n5((5))
        n3((3))
        n7((7))
        n1((1))
        n4((4))
        n5 --> n3
        n5 --> n7
        n3 --> n1
        n3 --> n4
    end
    style n5 fill:#4a90d9,stroke:#2d6aad,color:#fff
    style n3 fill:#4a90d9,stroke:#2d6aad,color:#fff
    style n7 fill:#4a90d9,stroke:#2d6aad,color:#fff
    style n1 fill:#6bb3f0,stroke:#4a90d9,color:#fff
    style n4 fill:#6bb3f0,stroke:#4a90d9,color:#fff

根 5：左子树 < 5，右子树 > 5；3 的左为 1、右为 4；7 无子节点。

二、AVL 树

2.1 平衡因子与平衡条件

AVL 树：任意结点的左右子树高度差（平衡因子）的绝对值 ≤ 1。
平衡因子 = 左子树高度 − 右子树高度；只可能为 −1、0、1。
插入/删除后若失衡，通过旋转恢复：单旋（LL/RR）、双旋（LR/RL）。

2.2 AVL 树示例（结构图）

下面为一棵平衡的 AVL 树（数值仅作形状示例，满足 BST 且各点平衡因子在 ±1 内）：

flowchart TB
    subgraph AVL["AVL 树示意"]
        direction TB
        r((根))
        L((左))
        R((右))
        LL((左左))
        LR((左右))
        RL((右左))
        RR((右右))
        r --> L
        r --> R
        L --> LL
        L --> LR
        R --> RL
        R --> RR
    end
    style r fill:#2d8a6e,stroke:#1e5c47,color:#fff
    style L fill:#2d8a6e,stroke:#1e5c47,color:#fff
    style R fill:#2d8a6e,stroke:#1e5c47,color:#fff
    style LL fill:#3db389,stroke:#2d8a6e,color:#fff
    style LR fill:#3db389,stroke:#2d8a6e,color:#fff
    style RL fill:#3db389,stroke:#2d8a6e,color:#fff
    style RR fill:#3db389,stroke:#2d8a6e,color:#fff

插入后若某点平衡因子为 2 或 −2，则在该点做 LL/RR 单旋或 LR/RL 双旋，使整棵树重新满足 AVL 条件。

三、红黑树（RBT）

3.1 五条性质

结点是红色或黑色。
根是黑色。
所有叶子（NIL）视为黑色。
红色结点的两个子结点都是黑色（不能有相邻红结点）。
从任意结点到其每个叶子的简单路径上，黑色结点数相同（黑高一致）。

由 4、5 可推出：从根到叶子的最长路径 ≤ 最短路径的 2 倍，故近似平衡，查找为 O(log n)。

3.2 插入与删除简述

插入：先按 BST 插入并着红色，再通过变色 + 旋转（左旋/右旋）满足上述性质；根强制染黑。
删除：按 BST 删除后，若破坏黑高或出现双红，则通过变色与旋转修复（分多种情况，核心是保持黑高与无相邻红）。

3.3 红黑树示例（结构图）

下面为一棵红黑树的结构与颜色示意（黑色与红色结点在图中用填充色区分，B=黑 R=红）：

flowchart TB
    subgraph RBT["红黑树示例"]
        direction TB
        N7["7 (B)"]
        N3["3 (B)"]
        N11["11 (R)"]
        N1["1 (R)"]
        N5["5 (R)"]
        N9["9 (B)"]
        N13["13 (B)"]
        N7 --> N3
        N7 --> N11
        N3 --> N1
        N3 --> N5
        N11 --> N9
        N11 --> N13
    end
    style N7 fill:#222,stroke:#111,color:#fff
    style N3 fill:#222,stroke:#111,color:#fff
    style N9 fill:#222,stroke:#111,color:#fff
    style N13 fill:#222,stroke:#111,color:#fff
    style N11 fill:#c0392b,stroke:#922b21,color:#fff
    style N1 fill:#c0392b,stroke:#922b21,color:#fff
    style N5 fill:#c0392b,stroke:#922b21,color:#fff

根 7 为黑；11 为红则其子 9、13 为黑；从根到各 NIL 路径上黑结点数相同。

3.4 红黑树与 AVL 对比（树高）

flowchart TB
    subgraph 选择
        direction TB
        A[查询多] --> RBT[红黑树]
        B[插入删除多且要严格平衡] --> AVL[AVL树]
    end

HashMap 在桶内使用红黑树，在保证 O(log n) 的同时，减少插入/删除时的旋转次数。

四、HashMap 整体结构（JDK 1.8）

4.1 数组 + 链表 + 红黑树

底层是桶数组 Node<K,V>[] table；每个桶里要么是链表（Node 用 next 串起来），要么在链表长度达到阈值且数组容量足够时树化为红黑树（TreeNode）。

4.2 HashMap 结构示意图（必含“树”）

下面表示：表头是数组，某桶为链表，某桶为红黑树。

flowchart TB
    subgraph table["table 桶数组"]
        direction TB
        T0["桶 0"]
        T1["桶 1"]
        T2["桶 2"]
        T3["桶 3"]
    end

    subgraph bucket1["桶内：链表"]
        direction TB
        A((Node))
        B((Node))
        C((Node))
        A --> B --> C
    end

    subgraph bucket2["桶内：红黑树"]
        direction TB
        R((根))
        R1((左))
        R2((右))
        R --> R1
        R --> R2
    end

    T0 --> bucket1
    T2 --> bucket2
    style R fill:#222,stroke:#111,color:#fff
    style R1 fill:#c0392b,stroke:#922b21,color:#fff
    style R2 fill:#222,stroke:#111,color:#fff

桶 0：链表，便于少量冲突时 O(1) 插入。
桶 2：红黑树，冲突多时查找 O(log n)。

4.3 桶内链表 → 红黑树（树化逻辑示意）

当同一桶内链表结点数 ≥ 8 且 数组长度 ≥ 64 时，该桶链表会变为红黑树；扩容后若树结点数 ≤ 6，会再退化为链表。

flowchart TB
    subgraph 树化条件
        direction TB
        A[链表长度 ≥ 8] --> C{数组长度 ≥ 64?}
        C -->|是| D[转为红黑树]
        C -->|否| E[先扩容]
    end

4.3.1 JDK 1.8：什么时候是链表、什么时候是红黑树？转换条件总结

桶内是链表的情况（满足其一即可）：

情况	说明
桶内结点数 < 8	未达到树化阈值，一直是链表
桶内结点数 ≥ 8 但 table.length < 64	只扩容不树化，该桶仍是链表（或扩容后分散到多个桶）
由红黑树退化而来	见下「红黑树 → 链表」

桶内是红黑树的情况：

该桶曾经满足「链表结点数 ≥ 8 且 table.length ≥ 64」，执行过 treeifyBin → treeify，当前仍是树且未触发退化。

链表 → 红黑树（树化）的触发条件（两个条件同时满足）：

该桶链表结点数达到 8：在 putVal 里尾插后，binCount >= TREEIFY_THRESHOLD - 1（即已有 8 个结点）时调用 treeifyBin(tab, hash)。
当前 table 长度 ≥ 64：treeifyBin 内若 tab.length < MIN_TREEIFY_CAPACITY（64），只做 resize() 不树化；只有 tab.length >= 64 时才把该桶的 Node 转成 TreeNode 并调用 hd.treeify(tab) 建红黑树。

因此：先看单桶是否满 8 个，再看表长是否 ≥ 64；表长不足 64 时优先扩容分散，不树化。

红黑树 → 链表（退化）的触发条件（满足即退化）：

resize 时：TreeNode.split() 把该桶树按 hash & oldCap 拆成两段挂到新表；若某段结点数 ≤ UNTREEIFY_THRESHOLD（6），该段会调用 untreeify 转回普通 Node 链表。
remove 时：在树中删除结点后，若根、左子、右子、左子的左子等为 null（即树过小），也会退化为链表（具体见 removeTreeNode 内逻辑）。

总结表：

转换方向	条件
链表 → 红黑树	① 该桶链表结点数 ≥ 8；② 且 `table.length ≥ 64`。二者同时满足才树化。
红黑树 → 链表	① resize 后该桶树拆成的一段结点数 ≤ 6；② 或 remove 导致树过小。

常量回顾：TREEIFY_THRESHOLD = 8（树化阈值）、UNTREEIFY_THRESHOLD = 6（退化阈值）、MIN_TREEIFY_CAPACITY = 64（允许树化的最小表长）。

4.4 哈希冲突与解决策略

什么是哈希冲突

哈希冲突：不同的 key 经 hash(key) 与 (n-1) & hash 计算后得到相同的桶下标，即多个键值对要放进同一个桶。

冲突无法从根本避免：桶数量 n 有限，key 空间通常远大于 n，必然存在不同 key 映射到同一 index。
冲突过多会导致单桶链表过长，查找从 O(1) 退化为 O(k)，k 为链长。

HashMap 的解决方式：链地址法（拉链法）

HashMap 采用链地址法：每个桶不直接存一个元素，而是存一条「链表」（或冲突多时升级为红黑树），同一桶内的结点都是「下标相同」的冲突项。

无冲突：tab[i] 为单结点，查找 O(1)。
有冲突：在桶内沿链表或树查找，先比 hash 再比 key；链表 O(k)，树 O(log k)。
冲突加剧：单桶结点数 ≥ 8 且 table 长度 ≥ 64 时树化，将最坏查找降为 O(log n)。

其他常见冲突解决方式（非 HashMap）：开放寻址（线性探测、二次探测）、再哈希等；链地址法实现简单，删除方便，且与树化结合可控制最坏情况。

五、HashMap 关键常量与字段（源码级）

5.1 核心常量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   // 16，默认桶数量
static final int MAXIMUM_CAPACITY = 1 << 30;         // 最大容量 2^30
static final float DEFAULT_LOAD_FACTOR = 0.75f;      // 默认负载因子
static final int TREEIFY_THRESHOLD = 8;              // 单桶链表长度≥8 时考虑树化
static final int UNTREEIFY_THRESHOLD = 6;            // 树结点≤6 时退化为链表
static final int MIN_TREEIFY_CAPACITY = 64;          // table 长度≥64 才执行树化

容量始终为 2 的幂，便于用 (n - 1) & hash 替代 hash % n，且位运算更快。
未指定容量时，threshold 在第一次 resize() 中赋为 newCapacity * loadFactor；指定容量时构造里会先通过 tableSizeFor(cap) 得到不小于 cap 的最小 2 的幂，再在 resize() 里赋给 table.length 并重算 threshold。

5.1.1 tableSizeFor：保证容量为 2 的幂

static final int tableSizeFor(int cap) {
    int n = cap - 1;           // 避免 cap 已是 2 的幂时返回 2*cap
    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;
}

通过多次「无符号右移 + 或」把最高位以下的位全部填成 1，再加 1 得到大于等于 cap 的最小 2 的幂（如 cap=10 → n+1=16）。构造 HashMap(initialCapacity) 时用该值作为第一次 resize() 的容量依据。

5.1.2 负载因子 0.75 与树化阈值 8/6

负载因子 0.75：threshold = capacity * 0.75，即平均每桶约 0.75 个元素时扩容。过小则空间浪费、扩容频繁；过大则冲突多、单桶链长。0.75 是经验上的空间与时间折中。
树化阈值 8 / 退化 6：源码注释中引用泊松分布，在良好的 hash 分布下，单桶结点数达到 8 的概率非常小；设为 8 可在极端情况下用树保性能，又避免过早树化。退化用 6 而非 8，避免在 7、8 之间反复树化/退化。

5.2 核心字段

transient Node<K,V>[] table;   // 桶数组，懒初始化：第一次 put 时才创建
transient int size;            // 当前键值对个数（≠ table.length）
int threshold;                 // 扩容阈值，size > threshold 时触发 resize
final float loadFactor;        // 负载因子，构造时指定，默认 0.75
transient int modCount;        // 结构性修改次数，用于迭代器 fail-fast

无参构造只设 loadFactor = 0.75f，table、threshold 为 0；带参构造会通过 tableSizeFor(initialCapacity) 算出初始 threshold，在第一次 resize() 时再赋给 table.length。

5.3 结点类型（源码结构）

链表结点 Node（HashMap.Node）：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;       // 存下来避免重复计算
    final K 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;
    }
}

红黑树结点 TreeNode（继承链：Node ← LinkedHashMap.Entry ← TreeNode）：

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;   // 删除时需断链，保留双向链
    boolean red;

    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
    // 树操作：rotateLeft、rotateRight、balanceInsertion、moveRootToFront 等
}

判断桶内是链表还是树：if (p instanceof TreeNode)；树根仍占 table[i] 位置，通过 left/right 走树结构。

六、hash 与下标计算（源码）

6.1 hash 方法

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

key 为 null：返回 0，因此 null 的 key 始终落在 table[0]（HashMap 只允许一个 null key，多个会覆盖）。
key 非 null：hashCode() 与「高 16 位无符号右移」做异或，把高位的随机性混入低位；因为下标用 (n-1) & hash 只取低若干位，若 n 较小而 hashCode 高位不同、低位相同，容易冲突，异或后可减轻这一问题。

6.2 下标计算

int n = table.length;
int index = (n - 1) & hash;   // 等价于 hash % n，且 n 为 2 的幂时成立

n 为 2 的幂时，n - 1 的二进制为低位全 1（如 15 = 0b1111），& 相当于取 hash 的低 log2(n) 位，结果在 [0, n-1]，等价于取模且更快。

七、put 流程与源码（putVal）

put(key, value) 内部调用 putVal(hash(key), key, value, false, true)，核心逻辑如下。

7.1 初始化与定位桶

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab;
    Node<K,V> p;
    int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;           // 懒初始化：第一次 put 时 resize 建表
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = new Node<>(hash, key, value, null);  // 桶为空，直接放新结点
    else {
        // 桶非空，见下
    }
    // ...
}

若 table 未初始化或长度为 0，先 resize() 得到新表并赋值给 tab，再算 i = (n - 1) & hash 得到桶下标；若 tab[i] == null，直接 new Node 放入，否则进入分支处理哈希冲突。

7.2 桶非空：树分支与链表分支

else {
    Node<K,V> e;
    K k;
    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 = new Node<>(hash, key, value, null);  // 尾插
                if (binCount >= TREEIFY_THRESHOLD - 1)        // 即链表已有 8 个结点
                    treeifyBin(tab, hash);                    // 可能树化或仅扩容
                break;
            }
            if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                break;   // 找到相同 key，e 指向该结点，后面覆盖
            p = e;
        }
    }
    if (e != null) {
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
}
++size;
if (size > threshold)
    resize();
return null;

首结点命中：p 的 hash、key 与当前 key 一致，则 e = p，后面统一写 e.value = value。
树分支：p instanceof TreeNode 时调用 putTreeVal，在红黑树中查找/插入，返回已存在结点或 null。
链表分支：沿 p.next 遍历；若到尾部仍未找到，则 p.next = new Node(...) 尾插，并判断 binCount >= 7（即当前链表共 8 个结点）时调用 treeifyBin(tab, hash)；若遍历中找到相同 key，则 e 指向该结点并 break，最后覆盖 e.value。
最后 ++size，若 size > threshold 则 resize()。

7.3 treeifyBin：树化条件

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index;
    Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)  // 即 n < 64
        resize();   // 不树化，只扩容，分散结点
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);   // 将当前桶的链表转成红黑树
    }
}

table 长度 < 64：只做 resize()，不树化，通过扩容降低单桶长度。
table 长度 ≥ 64 且该桶非空：将该桶的 Node 链转成 TreeNode 双链表（保留 prev/next），再调用 hd.treeify(tab) 在桶内构建红黑树并保持根在 tab[index]。

八、get 流程与源码（getNode）

get(key) 内部调用 getNode(hash(key), key)，返回对应结点中的 value（或 null）。

8.1 源码逻辑

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) {
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;   // 首结点命中
        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;
                e = e.next;
            } while (e != null);
        }
    }
    return null;
}

表未初始化或长度为 0：直接返回 null。
桶为空：first == null，返回 null。
首结点命中：先比 hash，再比 == 或 equals，命中则返回 first。
桶内还有结点：若 first instanceof TreeNode，调用 getTreeNode(hash, key) 在红黑树中按 key 查找（先比 hash，再 compareTo 或 equals）；否则沿 first.next 做 do-while 遍历链表，命中则返回该结点。
未找到：返回 null。

九、resize 流程与源码

9.1 新容量与新阈值

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 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;   // 新阈值 = 旧阈值 * 2
    }
    else if (oldThr > 0)
        newCap = oldThr;            // 构造时指定了 initialCapacity，第一次 resize 用该容量
    else {
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0)
        newThr = (int)(loadFactor * newCap);
    threshold = newThr;
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 迁移逻辑见下
    return newTab;
}

已初始化且未达上限：newCap = oldCap << 1，newThr = oldThr << 1（均为 2 倍，不超过 MAX）。
未初始化且构造时指定了容量：newCap = oldThr（之前 tableSizeFor 的结果），再 newThr = (int)(loadFactor * newCap)。
无参构造第一次 put：newCap = 16，newThr = 12。

9.2 迁移：为什么只可能落在「原下标」或「原下标 + oldCap」

if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {
        Node<K,V> e;
        if ((e = oldTab[j]) != null) {
            oldTab[j] = null;
            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 {
                Node<K,V> loHead = null, loTail = null;
                Node<K,V> hiHead = null, hiTail = null;
                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;
                    }
                    e = next;
                } while (e != null);
                if (loTail != null) { loTail.next = null; newTab[j] = loHead; }
                if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }
            }
        }
    }
}

单结点：e.hash & (newCap - 1) 得到新下标，放入新表。
链表：用 e.hash & oldCap 分两类——结果为 0 的挂在 loHead/loTail，保持顺序后整体放到 newTab[j]；结果为 1 的挂在 hiHead/hiTail，整体放到 newTab[j + oldCap]。原因：newCap = 2 * oldCap，(n-1)&hash 只多了一位，该位即 hash & oldCap，0 则新下标仍为 j，1 则新下标为 j + oldCap。
树：TreeNode.split(this, newTab, j, oldCap) 按同样规则拆成两段，每段再判断结点数：若 ≤ UNTREEIFY_THRESHOLD(6)，退化为链表；否则在 newTab 中重新树化（或保持为树）。

十、HashMap 演进过程（JDK 1.7 → 1.8）

10.1 对比总览

项目	JDK 1.7	JDK 1.8
桶内结构	仅链表	链表 + 红黑树（树化/退化）
插入方式	头插（易成环）	尾插
hash 计算	多次位运算	一次异或 `hashCode ^ (hashCode>>>16)`
扩容时机	先扩容再插入	先插入再判断是否扩容

10.2 结构演进：为何引入红黑树

1.7：桶内只有链表。在 hash 分布差或恶意构造大量冲突时，单桶链表很长，get/put 退化为 O(n)。
1.8：单桶结点数 ≥ 8 且 table 长度 ≥ 64 时树化为红黑树，最坏查找降为 O(log n)，同时保留链表在冲突少时的低开销。

10.3 头插改尾插与 1.7 扩容死链

1.7 头插：新结点插在桶头，newNode.next = table[i]; table[i] = newNode。扩容迁移时按头插顺序把旧桶结点迁到新表，多线程下：线程 A 与 B 同时扩容，若 A 在迁移某桶时挂起，B 完成该桶迁移并已反转链表，A 恢复后继续用旧引用做头插，可能形成环（next 互相指），后续 get 该桶会死循环。
1.8 尾插：新结点插在桶尾，迁移时保持原顺序挂到 lo/hi 链，不反转，不会因为多线程扩容在同一个桶上造出环；但 HashMap 仍非线程安全，并发 put 仍可能丢数据或结构错乱，需用 ConcurrentHashMap。

10.4 hash 计算简化

1.7：多次位运算扰动（不同版本实现略有差异），意图打散低位。
1.8：hashCode ^ (hashCode >>> 16) 一次完成，把高 16 位混入低 16 位，在保证分布的前提下减少计算量。

10.5 扩容时机

1.7：先判断是否需扩容，需要则先 resize()，再在新表上插入当前 key。
1.8：先插入（可能触发 treeifyBin），插入完成后若 size > threshold 再 resize()。逻辑更直观，且与树化判断（先插满 8 个再决定树化还是扩容）一致。

10.6 使用注意：线程安全与 key 的 equals/hashCode

线程安全

HashMap 非线程安全：多线程并发 put/remove 可能导致数据丢失、结构损坏或 1.7 下死链。需要线程安全时使用 ConcurrentHashMap，或对 HashMap 做外部同步（如 Collections.synchronizedMap）。
迭代器为 fail-fast：迭代过程中若检测到 modCount 变化会抛出 ConcurrentModificationException。

key 的 equals 与 hashCode 契约

作为 key 的对象必须正确实现 equals 与 hashCode：若 a.equals(b) 为 true，则 a.hashCode() == b.hashCode() 必须成立。
若只重写 equals 不重写 hashCode，两个「逻辑相等」的 key 可能得到不同 hash，从而落入不同桶，导致 put 后 get 不到、或重复 key 占多份。
反之，hashCode 相等不必 equals 相等（哈希冲突）；HashMap 会先比 hash 再比 equals 确定同一桶内是否同一 key。

十一、小结与树形结构回顾

二叉搜索树：左 < 根 < 右，中序有序；退化为链时 O(n)。上文用流程图画了 BST 示例。
AVL 树：平衡因子 ±1，通过旋转保持严格平衡；上文用流程图画了 AVL 形状示意。
红黑树：五条性质、近似平衡、插入删除通过变色与旋转修复；上文用流程图标了 B/R 的红黑树示例，并与 AVL 做了简单对比。
HashMap 源码：第五～九节按 JDK 8 源码细化了常量与字段、Node/TreeNode 结构、hash 与下标、putVal（含树化条件与 treeifyBin）、getNode、resize（新容量/阈值与迁移时 e.hash & oldCap 拆分链表/树），便于对照源码阅读。remove 与 get 类似：先 getNode 定位结点，再在链表或树中删除，树删除后若根为空或树结点数 ≤ 6 会退化为链表。
补充知识点：第四节后增加哈希冲突与链地址法；第五节增加 tableSizeFor、负载因子 0.75 与树化阈值 8/6 的说明；第十节扩展为 JDK 1.7 → 1.8 演进（结构、头插改尾插与 1.7 扩容死链、hash 简化、扩容时机），以及线程安全与 key 的 equals/hashCode 契约。

以上内容对应《Java 基础系列 - HashMap 源码分析》PDF 中的二叉搜索树、AVL、红黑树与 HashMap 源码解析部分，并自行补充了树形图、细化源码与冲突/演进/使用注意等知识点。