11.HashMap底层哈希设计

目录介绍

• 4.1 开篇疑问
• 4.2 哈希表的核心思想
  • 4.2.1 什么是哈希表
  • 4.2.2 哈希冲突的本质
  • 4.2.3 冲突解决策略对比
• 4.3 HashMap数据结构演进
  • 4.3.1 JDK7数组加链表
  • 4.3.2 JDK8引入红黑树
  • 4.3.3 为什么引入红黑树而非AVL树
  • 4.3.4 Node节点的数据结构
• 4.4 核心源码深度剖析
  • 4.4.1 hash方法的扰动设计
  • 4.4.2 put流程完整源码分析
  • 4.4.3 get流程分析
  • 4.4.4 扩容机制resize详解
  • 4.4.5 树化与退化机制
• 4.5 关键设计决策的数学原理
  • 4.5.1 容量为什么是2的幂
  • 4.5.2 tableSizeFor保证2的幂
  • 4.5.3 负载因子为什么是0.75
  • 4.5.4 链表转树阈值为什么是8
  • 4.5.5 为什么退化阈值是6而不是8
• 4.6 并发安全问题深度分析
  • 4.6.1 JDK7的死循环详解
  • 4.6.2 JDK8的数据覆盖问题
  • 4.6.3 ConcurrentHashMap的演进
  • 4.6.4 ConcurrentHashMap的size计算
• 4.7 HashMap的遍历与序列化
  • 4.7.1 遍历方式与性能对比
  • 4.7.2 fail-fast机制原理
  • 4.7.3 序列化的特殊处理
• 4.8 HashMap家族对比
  • 4.8.1 LinkedHashMap有序实现
  • 4.8.2 TreeMap排序实现
  • 4.8.3 WeakHashMap的缓存场景
• 4.9 生产环境最佳实践
• 4.10 总结与核心要点

4.1 开篇疑问

疑惑：HashMap 几乎是 Java 面试必问、工作必用的数据结构。为什么容量必须是 2 的幂次方？负载因子默认是 0.75？JDK 8 为什么引入红黑树而不是 AVL 树？多线程下 HashMap 会出什么问题？JDK 7 的扩容真的会导致死循环吗？

答疑：这些问题的答案都藏在 HashMap 的源码设计中。本篇从哈希表原理出发，逐步拆解每一个关键设计决策背后的深层逻辑，包括泊松分布的数学推导、位运算的精妙设计、并发场景下的致命问题。

4.2 哈希表的核心思想

4.2.1 什么是哈希表

哈希表（Hash Table）是根据键直接访问内存存储位置的数据结构。核心思想：

Key → hash(Key) → index → Value

理想情况下查找、插入、删除操作时间复杂度为 O(1)：

数据结构	查找	插入	删除
数组（按值查找）	O(n)	O(n)	O(n)
有序数组（二分查找）	O(log n)	O(n)	O(n)
平衡二叉搜索树	O(log n)	O(log n)	O(log n)
哈希表	O(1) 平均	O(1) 平均	O(1) 平均

哈希函数的核心要求：

1. 确定性：同一个 key 必须映射到同一个 index
2. 均匀性：不同的 key 应尽量均匀地分布到不同的 index
3. 高效性：计算过程要快

4.2.2 哈希冲突的本质

鸽巢原理（Pigeonhole Principle）：如果有 n+1 只鸽子要放进 n 个巢中，必然有一个巢至少有两只鸽子。

哈希表容量为 16，可能存入的 key 有无穷多个。无论哈希函数设计得多好，冲突不可避免。

// 不同的 key 可能有相同的 hashCode
"Aa".hashCode();    // 2112
"BB".hashCode();    // 2112
// 更极端：任意两个字符串都可能碰撞到同一个桶

4.2.3 冲突解决策略对比

策略	原理	优点	缺点	典型实现
链地址法	同一桶的元素组成链表	实现简单、删除方便	缓存不友好	Java HashMap
开放寻址法	冲突后探测下一个空位	缓存友好	删除复杂、负载因子不能太高	Python dict
再哈希法	用多个哈希函数	分散性好	计算开销大	布隆过滤器
公共溢出区	冲突元素放到单独区域	冲突少时高效	冲突多时性能差	—

HashMap 选择链地址法，JDK 8 在链表过长时升级为红黑树，是两种策略的结合。

4.3 HashMap数据结构演进

4.3.1 JDK7数组加链表

JDK 7 的 HashMap 结构是数组 + 链表：

table[] (Entry数组)
  [0] → null
  [1] → Entry(k1,v1) → Entry(k5,v5) → Entry(k9,v9) → null
  [2] → Entry(k2,v2) → null
  [3] → null
  ...
  [15] → Entry(k7,v7) → null

每个 Entry 包含四个字段：

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;    // 指向下一个冲突元素
    int hash;           // 缓存 hashCode
}

JDK 7 关键特点：

• 新元素使用头插法插入链表（时间复杂度 O(1)）
• 扩容时链表会反转（因为头插法重新插入）

4.3.2 JDK8引入红黑树

JDK 8 的结构演进为数组 + 链表 + 红黑树：

table[] (Node数组)
  [0] → null
  [1] → Node → Node → null                    (链表，≤8个)
  [2] → TreeNode(红黑树根)                      (链表长度>8 且数组长度≥64 时转树)
  ...

JDK 8 两个重大改变：

1. 链表长度 > 8 且数组长度 ≥ 64 时转红黑树，< 6 退化为链表
2. 插入从头插法改为尾插法（解决并发扩容死循环）

4.3.3 为什么引入红黑树而非AVL树

疑惑：AVL 树是严格平衡的，查找效率更高，为什么不用 AVL 树？

论证：HashMap 的使用场景决定了选择：

特性	AVL 树	红黑树
平衡度	严格平衡（左右子树高度差≤1）	近似平衡（最长路径≤最短路径的2倍）
查找性能	略优（树更矮）	稍逊（树略高）
插入/删除	旋转操作多（最多 O(log n) 次）	旋转操作少（最多 3 次）
适用场景	查找密集型	增删改频繁型

HashMap 中的树节点需要频繁插入和删除（put/remove），红黑树的旋转操作更少（插入最多 2 次旋转，删除最多 3 次旋转），维护平衡的开销更低。AVL 树虽然查找略快，但在 HashMap 这种增删频繁的场景下，综合性能不如红黑树。

4.3.4 Node节点的数据结构

// JDK 8 的 Node 节点
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;       // hashCode 的扰动结果
    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;
    }
}

// 红黑树节点（继承自 LinkedHashMap.Entry，间接继承 Node）
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 继承链为 TreeNode → LinkedHashMap.Entry → HashMap.Node，这意味着 TreeNode 同时保留了链表结构（next 指针），方便树退化为链表时使用。

4.4 核心源码深度剖析

4.4.1 hash方法的扰动设计

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

逐步分析：

假设 key.hashCode() = 0b 1111_1111_1010_0110_0000_0001_0011_0101

原始 hashCode:    1111 1111 1010 0110 | 0000 0001 0011 0101
                  ← 高16位 →           ← 低16位 →

h >>> 16:         0000 0000 0000 0000 | 1111 1111 1010 0110
                                        ← 高16位右移到低16位 →

XOR 结果:         1111 1111 1010 0110 | 1111 1110 1001 0011
                                        ← 低16位融合了高16位信息 →

桶索引计算: (n-1) & hash
当 n=16:  n-1 = 0000 0000 0000 0000 0000 0000 0000 1111
          只用到了低4位！
          
如果不做扰动：低4位 = 0101 → index = 5
做了扰动后：  低4位 = 0011 → index = 3

高16位的信息参与了桶定位，减少了只靠低位分布不均的冲突

疑惑：JDK 7 的 hash 方法做了 4 次移位和 4 次异或，JDK 8 为什么只做了 1 次？

论证：JDK 8 引入了红黑树兜底极端冲突场景，不再需要过度依赖 hash 分散来防止性能退化。1 次右移 + 1 次异或已经足够将高位信息混入低位，多次扰动的额外收益不大，却增加了计算开销。

null key 的特殊处理：hash(null) 返回 0，即 null 键固定放在 table[0]。HashMap 允许一个 null key 和多个 null value。

4.4.2 put流程完整源码分析

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) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 步骤1: 数组为空则初始化（懒加载）
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // 步骤2: 计算桶位置，桶为空直接放入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        
        // 步骤3: 桶的第一个节点就是目标key
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        
        // 步骤4: 桶是红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        
        // 步骤5: 桶是链表
        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;
                p = e;
            }
        }
        
        // 步骤6: 如果找到了相同key的节点，更新value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);     // LinkedHashMap 的回调
            return oldValue;
        }
    }
    
    ++modCount;  // 结构修改次数（fail-fast 机制）
    
    // 步骤7: 超过阈值则扩容
    if (++size > threshold)
        resize();
    
    afterNodeInsertion(evict);  // LinkedHashMap 的回调
    return null;
}

流程图：

put(key, value)
  → 计算 hash = hash(key)
    → table == null？→ resize() 初始化
    → 计算桶位置 i = (n-1) & hash
      → tab[i] == null？→ 直接放入新节点
      → tab[i] 不为空：
        → 第一个节点 key 相同？→ 记录为 e，待更新
        → 是 TreeNode？→ 红黑树的 putTreeVal()
        → 是链表？→ 尾插法遍历
          → 找到相同 key？→ 记录为 e，待更新
          → 到尾部？→ 插入新节点
            → 链表长度 ≥ 8？→ treeifyBin()
      → e != null？→ 更新旧值
    → ++size > threshold？→ resize() 扩容

关键设计细节：

1. 懒加载：首次 put 才创建数组，节省内存
2. 先比较 hash 再比较 equals：hash 比较是 int 比较（O(1)），equals 可能耗时
3. 尾插法：链表新节点插到末尾，避免了 JDK 7 头插法的并发死循环
4. modCount：每次结构修改递增，Iterator 用它检测并发修改

4.4.3 get流程分析

public V get(Object key) {
    Node<K,V> e;
    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) {
        
        // 检查第一个节点（大部分桶只有一个元素，这步就返回了）
        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;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

性能分析：

• 最好情况 O(1)：桶中只有一个元素（负载因子 0.75 时约 60% 的桶为空，30% 只有 1 个元素）
• 链表情况 O(k)：k 为链表长度
• 红黑树情况 O(log k)：k 为树中节点数

4.4.4 扩容机制resize详解

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;  // 阈值也翻倍
    }
    // ...初始化逻辑省略
    
    // 重新分配所有元素
    Node<K,V>[] newTab = new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;  // help GC
                
                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 {
                    // 链表的拆分——JDK 8 的精妙优化
                    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 {
                            // 移到新位置 = 原位置 + oldCap
                            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;
                    }
                }
            }
        }
    }
    return newTab;
}

精妙的位运算判断：

旧容量 oldCap = 16 = 0001 0000

hash = 5  (0000 0101):  hash & oldCap = 0000 0000 = 0  → 留在 index=5
hash = 21 (0001 0101):  hash & oldCap = 0001 0000 ≠ 0  → 移到 index=5+16=21

原理：容量翻倍意味着 (n-1) 多了一个高位 1
旧 n-1 = 0000 1111  (只看低4位)
新 n-1 = 0001 1111  (看低5位)

多出来的那个 bit（第5位）决定了元素去向：
  该 bit 为 0 → 留在原位
  该 bit 为 1 → 移到 原位置 + oldCap

对比 JDK 7 的扩容：JDK 7 需要重新计算每个元素的 hash & (newCap-1) 索引。JDK 8 只需一次位运算判断即可，更高效。

4.4.5 树化与退化机制

树化条件（两个条件都要满足）：

1. 链表长度 ≥ 8（TREEIFY_THRESHOLD）
2. 数组长度 ≥ 64（MIN_TREEIFY_CAPACITY）

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 数组长度 < 64 时优先扩容，而非树化
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 链表节点转为 TreeNode，然后构建红黑树
        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);  // 构建红黑树
    }
}

疑惑：为什么数组长度 < 64 时不树化？

论证：数组小的时候，冲突严重通常是因为数组太小而非 hash 分布差。扩容就能解决问题，而树化开销大（TreeNode 占用内存是普通 Node 的 2 倍多）。只有数组已经足够大，链表还很长，才说明确实需要树化。

退化条件：

• 扩容 split 后，树节点数 ≤ 6 时退化为链表
• 红黑树的根节点为 null、根的左右子树或左子树的左子树为 null 时退化

4.5 关键设计决策的数学原理

4.5.1 容量为什么是2的幂

原因一：位运算代替取模

// 取模运算：hash % n
// 等价位运算：hash & (n-1)，仅在 n 是 2 的幂时成立

// 证明：当 n = 2^k 时，n-1 的二进制是 k 个 1
// n = 16 = 10000, n-1 = 01111
// hash & 01111 ≡ hash % 10000
// 因为 AND 操作只保留低 k 位，等于对 2^k 取模

// 性能差异：位运算比取模快 5-10 倍

原因二：扩容时元素位置可预测（前面已详述）

原因三：保证哈希分布均匀

n-1 全是 1：      1111 1111 1111 1111
hash & (n-1)：     每一位都有效，分布均匀

如果 n 不是 2 的幂，比如 n = 12：
n-1 = 1011
hash & 1011：     第2位始终为0
桶 index 为 x1xx 的永远不会被命中
有效桶数只有 8 个而非 12 个

4.5.2 tableSizeFor保证2的幂

即使你传入的初始容量不是 2 的幂，HashMap 也会自动调整：

// 将传入的 cap 向上取整到最近的 2 的幂
static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

// JDK 8 的经典位运算写法：
static final int tableSizeFor(int cap) {
    int n = cap - 1;   // 防止 cap 已经是 2 的幂时多扩一倍
    n |= n >>> 1;      // 最高位的 1 扩展到相邻低位
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;     // 最终 n 的有效位全变成 1
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

// 示例：cap = 10
// n = 9 = 1001
// n |= n>>>1 → 1001 | 0100 = 1101
// n |= n>>>2 → 1101 | 0011 = 1111
// n |= n>>>4 → 1111 | 0000 = 1111
// ...
// n + 1 = 10000 = 16

精妙之处：通过 5 次位或运算，将最高位的 1 传播到所有低位，然后 +1 得到 2 的幂。整个过程没有循环，固定 5 步完成。

4.5.3 负载因子为什么是0.75

负载因子 = 元素个数 / 数组长度。0.75 是空间利用率和查找效率的最佳平衡点。

数学推导：假设哈希函数理想均匀，每个桶的元素数服从泊松分布 P(X=k) = (λ^k × e^(-λ)) / k!，其中 λ = 负载因子。

当 λ = 0.75 时，桶中元素个数的概率分布：
P(0) = 0.47237    → 47% 的桶为空
P(1) = 0.35428    → 35% 的桶有1个元素
P(2) = 0.13285    → 13% 的桶有2个元素
P(3) = 0.03321    →  3% 的桶有3个元素
P(4) = 0.00623    → 0.6%
P(5) = 0.00093    → 0.09%
P(6) = 0.00012    → 0.01%
P(7) = 0.00001    → 0.001%
P(8) = 0.00000006 → 千万分之六

如果负载因子过小（如 0.5）：

• 47% → 60% 的桶为空，空间严重浪费
• 扩容更频繁，每次扩容都要重新分配和复制

如果负载因子过大（如 1.0）：

• 每个桶平均 1 个元素，冲突概率显著增加
• 平均链表长度增加，查找退化

0.75 是实验和理论兼顾的选择：空间利用率约 75%，平均链表长度约 0.5（大部分桶 0~1 个元素），查找性能接近 O(1)。

4.5.4 链表转树阈值为什么是8

结合上面泊松分布的计算，负载因子 0.75 时链表长度达到 8 的概率是 0.00000006（千万分之六）。

选择 8 的理由：
1. 正常情况下不会触发树化 → 避免红黑树的额外开销
   - TreeNode 占用内存约是 Node 的 2.5 倍
   - 红黑树需要维护平衡（旋转操作）
   
2. 极端情况下能兜底 → 防止 Hash DoS 攻击
   - 攻击者构造大量哈希碰撞的 key
   - 链表退化为 O(n)，红黑树保证 O(log n)
   
3. 与退化阈值 6 配合，留出缓冲区间

4.5.5 为什么退化阈值是6而不是8

疑惑：为什么不在链表长度降到 8 以下时就退化？

论证：如果树化和退化的阈值相同，当链表长度在阈值附近频繁增减时，会反复在链表和红黑树之间切换，即"乒乓效应"（thrashing）。

假设阈值都是 8：
插入第8个元素 → 树化（开销大）
删除1个元素   → 退化为链表（开销大）
再插入1个元素 → 又树化
...频繁切换，性能严重下降

设置为 6：
插入第8个元素 → 树化
删除到7个     → 仍是树（不退化）
删除到6个     → 退化为链表
// 中间有 2 个元素的缓冲区间，避免频繁切换

4.6 并发安全问题深度分析

4.6.1 JDK7的死循环详解

JDK 7 的 resize() 使用头插法迁移链表元素，多线程并发扩容时可能形成环形链表。

详细过程：

初始状态，table[1] 的链表：A → B → C → null

线程1 开始扩容，记录了：
  e = A, next = B

线程1 被挂起（时间片用完）

线程2 完成扩容，由于头插法，新链表变为：
  newTable[1]: C → B → A → null

线程1 恢复执行，但线程1 还记得 e=A, next=B：
  第1轮：头插法，A 放到 newTable[1] 头部
         newTable[1]: A → null
  
  第2轮：e = B, next = B.next
         但此时 B.next 已被线程2 改为 A！
         next = A
         头插法，B 放到头部
         newTable[1]: B → A → null
  
  第3轮：e = A（next 记的）
         A.next = newTable[1] 头部 = B
         A → B → A → B → ...  死循环！

最终结构：
newTable[1]: B ⟷ A  （A.next=B, B.next=A，形成环）

后续任何 get(key) 如果 hash 到 table[1]，遍历链表时就会死循环
CPU 飙升到 100%

4.6.2 JDK8的数据覆盖问题

JDK 8 改为尾插法，解决了死循环，但并发 put 仍有问题：

问题一：数据覆盖

// 两个线程同时 put 不同的 key，但 hash 到同一个空桶
// 线程A 和线程B 都执行到：
if ((p = tab[i = (n - 1) & hash]) == null)
// 两者都发现桶为空

tab[i] = newNode(hash, key, value, null);
// 线程A 先放入，线程B 后放入，覆盖了线程A 的数据

问题二：size 计数不准确

// ++size 不是原子操作
// 两个线程同时 put，各自 ++size
// 可能 size 只增加了 1 而不是 2
// 导致扩容时机不准确

问题三：树化过程中数据不一致

// 一个线程在树化，另一个线程在同一个桶上操作
// 可能导致树结构损坏

4.6.3 ConcurrentHashMap的演进

JDK 7：分段锁

┌──────────────────────────────────────────┐
│ Segment[0]    Segment[1]    ...  Segment[15] │
│ ┌──────┐    ┌──────┐           ┌──────┐     │
│ │Lock+│    │Lock+│           │Lock+│     │
│ │Entry│    │Entry│           │Entry│     │
│ │数组  │    │数组  │           │数组  │     │
│ └──────┘    └──────┘           └──────┘     │
└──────────────────────────────────────────┘
每个 Segment 独立加锁，默认 16 段，最多支持 16 个线程并发

JDK 8：CAS + synchronized 锁单个桶

final V putVal(K key, V value, boolean onlyIfAbsent) {
    // ...
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();  // CAS 初始化
        
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 桶为空，CAS 无锁插入
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
                break;
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);  // 协助扩容
        
        else {
            synchronized (f) {  // 锁住桶的头节点
                // 链表/红黑树操作
            }
        }
    }
}

演进对比：

特性	JDK 7 ConcurrentHashMap	JDK 8 ConcurrentHashMap
锁粒度	Segment（段锁）	Node（桶锁）
并发度	默认 16	数组长度（可达数万）
数据结构	数组+链表	数组+链表+红黑树
空桶插入	段锁	CAS 无锁
hash 计算	Wang/Jenkins hash	spread()

4.6.4 ConcurrentHashMap的size计算

JDK 8 的 ConcurrentHashMap 使用类似 LongAdder 的方式计算 size：

// 核心字段
private transient volatile long baseCount;        // 基础计数
private transient volatile CounterCell[] counterCells;  // 分段计数

// 计数逻辑
// CAS 更新 baseCount，失败时分散到 CounterCell 数组
// size() 返回 baseCount + Σ(counterCells[i].value)

// 这种设计避免了所有线程竞争同一个计数器
// 类似于 JDK 8 的 LongAdder

4.7 HashMap的遍历与序列化

4.7.1 遍历方式与性能对比

HashMap<String, Integer> map = new HashMap<>();

// 方式1：entrySet 遍历（推荐，一次获取 key 和 value）
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
}

// 方式2：keySet 遍历（每次 get 一次额外查找）
for (String key : map.keySet()) {
    Integer value = map.get(key);  // 额外的 hash + 查找
}

// 方式3：values 遍历（只需要 value 时）
for (Integer value : map.values()) {
    // ...
}

// 方式4：JDK 8 forEach
map.forEach((key, value) -> {
    // ...
});

// 方式5：Stream
map.entrySet().stream()
    .filter(e -> e.getValue() > 10)
    .forEach(e -> System.out.println(e.getKey()));

性能对比：entrySet ≈ forEach > keySet（keySet 多了一次 get 查找）。

4.7.2 fail-fast机制原理

// HashMap 内部维护 modCount，每次结构修改（put/remove）递增
transient int modCount;

// Iterator 初始化时记录当前 modCount
HashIterator() {
    expectedModCount = modCount;
    // ...
}

// 每次 next() 时检查
final Node<K,V> nextNode() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    // ...
}

注意：fail-fast 不是线程安全机制，它只是尽力检测并发修改。在多线程环境下应使用 ConcurrentHashMap。

// 常见错误：遍历时删除元素
for (String key : map.keySet()) {
    if (key.startsWith("temp")) {
        map.remove(key);  // ConcurrentModificationException!
    }
}

// 正确做法1：使用 Iterator.remove()
Iterator<Map.Entry<String, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
    if (it.next().getKey().startsWith("temp")) {
        it.remove();  // 安全删除
    }
}

// 正确做法2：JDK 8 removeIf
map.entrySet().removeIf(e -> e.getKey().startsWith("temp"));

4.7.3 序列化的特殊处理

HashMap 的 table 数组声明为 transient，不参与默认序列化：

transient Node<K,V>[] table;

疑惑：为什么不直接序列化 table？

论证：

1. hashCode 不可移植：不同 JVM 版本的 Object.hashCode() 实现可能不同，序列化后反序列化到另一台机器，元素可能在错误的桶中
2. 稀疏数组浪费空间：table 中大部分桶为 null，序列化这些 null 很浪费
3. 自定义序列化：HashMap 重写了 writeObject/readObject，只序列化 key-value 对，反序列化时重新 hash 放入桶中

4.8 HashMap家族对比

4.8.1 LinkedHashMap有序实现

LinkedHashMap 在 HashMap 基础上维护了一条双向链表，保证插入顺序或访问顺序：

// LinkedHashMap.Entry 额外维护双向链表
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;  // 双向链表指针
}

// accessOrder = false（默认）：按插入顺序
// accessOrder = true：按访问顺序（LRU 缓存）
LinkedHashMap<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true);

实现 LRU 缓存：

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;
    
    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true);  // accessOrder = true
        this.maxSize = maxSize;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;  // 超过容量时移除最久未访问的
    }
}

4.8.2 TreeMap排序实现

TreeMap 基于红黑树实现，按 key 的自然顺序或自定义 Comparator 排序：

TreeMap<String, Integer> map = new TreeMap<>();
map.put("banana", 2);
map.put("apple", 1);
map.put("cherry", 3);
// 遍历顺序：apple → banana → cherry（字典序）

// 支持范围查询
map.subMap("b", "d");     // banana, cherry
map.headMap("c");          // apple, banana
map.tailMap("b");          // banana, cherry

4.8.3 WeakHashMap的缓存场景

WeakHashMap 的 key 是弱引用，当 key 没有其他强引用时会被 GC 回收：

WeakHashMap<Object, String> cache = new WeakHashMap<>();
Object key = new Object();
cache.put(key, "value");

System.out.println(cache.size());  // 1
key = null;  // 断开强引用
System.gc();
System.out.println(cache.size());  // 0（key 被回收，entry 也被清除）

适用场景：缓存元数据、ClassLoader 相关的映射等。

4.9 生产环境最佳实践

1. 初始容量预估：

// 错误：使用默认容量，可能多次扩容
Map<String, Object> map = new HashMap<>();
for (int i = 0; i < 1000; i++) {
    map.put("key" + i, value);
}
// 扩容：16→32→64→128→256→512→1024→2048，共7次扩容

// 正确：预估容量
// 目标容量 = 预期元素数 / 负载因子 + 1
Map<String, Object> map = new HashMap<>(1334);  // 1000/0.75+1 ≈ 1334
// 实际容量 tableSizeFor(1334) = 2048，0次扩容

// 或者使用 Guava
Map<String, Object> map = Maps.newHashMapWithExpectedSize(1000);

2. key 的选择：

// 最佳 key：不可变对象（String、Integer 等包装类型）
// 原因：hashCode 不会变化，equals 行为一致

// 危险：可变对象作为 key
List<String> list = new ArrayList<>();
list.add("a");
map.put(list, "value1");
list.add("b");                    // 修改了 key
map.get(list);                    // null！hashCode 变了，找不到了

3. 合理使用 computeIfAbsent：

// JDK 8 之前
Map<String, List<String>> map = new HashMap<>();
List<String> list = map.get(key);
if (list == null) {
    list = new ArrayList<>();
    map.put(key, list);
}
list.add(value);

// JDK 8+：一行搞定
map.computeIfAbsent(key, k -> new ArrayList<>()).add(value);

4.10 总结与核心要点

HashMap 设计哲学：

1. 位运算代替算术运算：hash 扰动、容量 2 的幂、扩容位判断，处处用位运算提升性能
2. 概率论指导参数选择：负载因子 0.75、树化阈值 8，都基于泊松分布的数学推导
3. 渐进式优化：懒加载数组、链表→红黑树的渐进树化、扩容时的原地分裂
4. 空间与时间的平衡：负载因子就是空间和时间的权衡器

技术演变总结：

版本	数据结构	冲突处理	插入方式	并发安全	扩容方式
JDK 7	数组+链表	链地址法	头插法	不安全（死循环）	重新 hash 每个元素
JDK 8	数组+链表+红黑树	链地址法+树化	尾插法	不安全（数据覆盖）	位运算判断高低位
CHM 7	分段数组+链表	分段锁	头插法	Segment 锁	段内扩容
CHM 8	数组+链表+红黑树	CAS+sync	尾插法	桶级锁	多线程协助扩容

核心源码方法速览：

方法	作用	关键逻辑
hash()	扰动函数	高16位异或低16位
putVal()	插入元素	懒加载+尾插法+树化
getNode()	查找元素	先检查首节点+链表/树查找
resize()	扩容	容量翻倍+位运算分裂链表
treeifyBin()	链表转红黑树	数组≥64才树化
tableSizeFor()	容量取整	5次位或运算

理解 HashMap 的底层原理，是掌握 Java 集合框架乃至数据结构设计思维的关键一步。