HashMap 与 ConcurrentHashMap

一句话：HashMap 用「数组 + 链表 + 红黑树」把哈希冲突的查找从 O(n) 降到 O(log n)，用 0.75 的负载因子在空间和冲突之间折中；ConcurrentHashMap 把锁拆到单个桶，用 CAS 和无锁读换并发，代价是弱一致性和不允许 null。

适用 JDK 17 / JDK 21。JDK 7 的 Segment 分段锁和头插法只作为历史对照。

为什么需要

数组按下标访问是 O(1)，但 key 是任意对象，必须先映射成下标。哈希冲突不可避免：不同 key 可能落到同一个桶。冲突多了，链表退化成 O(n)，查询变慢，极端情况下还能被构造出大量碰撞拖垮 CPU。

HashMap 用树化兜底，ConcurrentHashMap 还要解决多线程并发写时的数据覆盖和扩容竞争。两者的核心问题相同：在桶级别控制冲突，在表级别控制扩容。

核心机制

HashMap 的数据结构

底层是 Node<K,V>[] table，每个桶挂链表；链表长度达到阈值后转红黑树。
默认初始容量 16，负载因子 0.75（JDK 8+）。阈值 threshold = capacity × loadFactor，元素数超过阈值就扩容。
容量必须是 2 的幂。下标用 (n - 1) & hash 代替取模，n 是 2 的幂时二者等价，而且扩容时只需看 hash 的一个新高位。
哈希扰动是 h ^ (h >>> 16)，把高 16 位混进低位，减少低位相同导致的碰撞。

树化的真实条件

JDK 8 的常量是 TREEIFY_THRESHOLD=8、UNTREEIFY_THRESHOLD=6、MIN_TREEIFY_CAPACITY=64。插入后某个桶的节点数达到 8，会调用 treeifyBin，但它先检查表长度：

text

binCount >= 8
  → table == null 或 table.length < 64
       → resize()，先扩容，不树化
  → 否则把链表转成红黑树

所以「链表长度到 8 就变红黑树」是错的，表长不到 64 时优先扩容。树退化回链表的阈值是 6，留出 7 这个缓冲，避免在 6/8 之间反复转换。

泊松分布常被用来解释「8 很少发生」：在随机哈希、负载因子 0.75 的假设下，一个桶里达到 8 个节点的概率约 0.00000006（JDK 8 HashMap 类注释）。这是树化阈值的合理性依据，不是 0.75 的推导过程。0.75 本身是时间与空间的折中：太低会频繁扩容，太高会让冲突和链表变长。

扩容与迁移

JDK 8 扩容时容量翻倍，每个桶的节点按 (e.hash & oldCap) == 0 拆成低位链和高位链：低位留在原下标，高位去 原下标 + oldCap。链表保持相对顺序，不需要重新计算 hash。

JDK 7 用头插法迁移，多线程并发扩容可能把链表反转成环，get 时死循环。JDK 8 改成尾插，环的问题消失，但 put 仍然不是原子的，并发写会丢数据，所以 HashMap 依然不是线程安全的。

ConcurrentHashMap 的并发写入

JDK 8 的 CHM 不再用 Segment，结构是 Node<K,V>[] table：

操作	做法
空桶插入	CAS 把新节点放到桶头，失败就重试
非空桶插入	`synchronized` 锁住桶的头节点，再遍历链表/树
读	`Node.val` 和 `next` 用 volatile 语义发布，读不加锁
扩容	多线程通过 `ForwardingNode` 协助迁移，`sizeCtl` 协调
计数	`baseCount` + `CounterCell[]`，类似 `LongAdder`，避免所有线程争一个计数

get 不加锁不等于读到「最新一致快照」：它保证不会读到坏结构，但不保证跨多个 key 的原子性。size() 是估计值，mappingCount() 返回 long，也仍是弱一致。

CHM 不允许 null key 和 null value。原因是并发下 get(key)==null 无法区分「key 不存在」和「value 是 null」，而 containsKey 与 get 之间可能被其他线程修改，无法用两次调用补回来。

实战场景

一、并发写 `HashMap`，缓存里凭空少了一半数据

现象：一个本地缓存用 HashMap 承载，读多写少，日常看不出问题。某次流量高峰后统计发现缓存条目数远小于应有值（约 6 成），并伴随偶发 ConcurrentModificationException；重启后正常，几小时后再次出现。

排查：JDK 8 的并发写不会再形成链表成环（那是 JDK 7 头插法扩容时的问题），但丢数据、size 不一致、遍历时抛异常依然会发生。

症状	机制
数据凭空消失	两个线程同时 `put` 到同一桶，或同时触发 `resize`，后写覆盖前写
`size` 与遍历结果不一致	`++size` 非原子；`threshold` 判断与插入交错
`ConcurrentModificationException`	迭代时 `modCount` 被其他线程改动
读到半构造的表	`table` 扩容期间另一个线程看到旧的引用数组
树化时抛异常	并发修改红黑树结构，父指针与颜色位不一致

“JDK 8 修了死循环”不等于“JDK 8 可以并发用 HashMap”。

对症做法：

java

// 1. 并发场景直接用 ConcurrentHashMap，且用原子方法而不是“检查再写”
private final Map<Long, Profile> cache = new ConcurrentHashMap<>(1024);

// 2. 容量预置：按预估条目数 ÷ 0.75 上取 2 的幂，避免边写边扩容
Map<Long, Profile> c = new ConcurrentHashMap<>(expectedSize * 4 / 3 + 1);

// 3. 只读为主 + 定期整体替换：用不可变快照换引用，读侧完全无锁
private volatile Map<Long, Profile> snapshot = Map.of();
void refresh() { snapshot = Map.copyOf(buildNew()); }        // 原子换引用，不存在中间态

复盘要点：判据是“静态扫描：被多线程访问的字段不出现 new HashMap<>()”——IDE 检查、Error Prone 的 MutableConcurrentMap 类规则都能挡住。同时要记住 HashMap 的三个设计常量（默认容量 16、负载因子 0.75、容量必须是 2 的幂）是为了单线程效率与扩容成本服务的，它们都不包含并发语义。

二、`containsKey` + `put` 不是原子，客户端被初始化三次

现象：路由表构建时用 ConcurrentHashMap，写法是 if (!map.containsKey(k)) map.put(k, buildExpensive(k));。压测发现同一个下游集群被初始化 3 次，连接池建了三套，其中一个没被关闭，最终端口与文件句柄被吃满（数小时后出现 Too many open files）。

排查：ConcurrentHashMap 保证单个方法原子，不保证“读—判断—写”这段代码原子。

组合	是否安全	说明
`containsKey` → `put`	不安全	两步之间可被插入
`get` → `put`（值计算）	不安全	两个线程各算一份，后写覆盖前者，泄漏前者资源
`computeIfAbsent`	安全	同 bin 加锁，映射函数只执行一次
`putIfAbsent`	安全	原子插入并返回旧值
`merge`	安全	计数/累加类场景的标准写法

java

// 正确：把“构建”放进 computeIfAbsent，同一个 key 只会构建一次
private final ConcurrentHashMap<String, ConnectionPool> pools = new ConcurrentHashMap<>();

ConnectionPool pool(String cluster) {
    return pools.computeIfAbsent(cluster, k -> newPool(k));   // 建池失败要抛异常，不留半成品
}

复盘要点：还有一条容易忽略的约束——映射函数里不能递归操作同一个 map：computeIfAbsent 的函数内部再次对同一 key 空间 put/compute 会抛 IllegalStateException: Recursive update；耗时构建放在函数里也会长时间占住该 bin，其他线程访问同 bin 会被阻塞。构建成本高时改成“先构建到局部变量，再 putIfAbsent + 关闭多余实例”：

java

// 构建成本高、不希望阻塞同 bin 时的写法
ConnectionPool mine = newPool(cluster);                 // 锁外构建
ConnectionPool old = pools.putIfAbsent(cluster, mine);
if (old != null) { mine.closeQuietly(); return old; }   // 竞争失败就关掉自己建的，不泄漏
return mine;

判据是“computeIfAbsent 的映射函数里没有远程调用/阻塞 IO”，以及“同一 key 的资源构建次数为 1”；后者用构建计数指标验证，成本很低。

三、自定义 key 的 `hashCode` 返回常量，get 变成线性扫描

现象：一个匹配引擎用 Map<RouteKey, Handler> 做查找，RouteKey 只重写了 equals，hashCode 用了 IDE 生成的 return 1;（后来被“优化”成缓存 hash 值时写错）。功能测试全通过，因为 equals 是对的；但缓存达到 5 万条后单次查找从 1μs 变成 400μs，接口 P99 撑不住。

排查：桶定位靠 hash，equals 只负责桶内比较。

环节	出错表现	判据来源
下标计算 `(n - 1) & hash`	hash 恒定 → 全落同一桶	容量是 2 的幂时等价取模
扰动 `h ^ (h >>> 16)`	高位不参与分布时无效	扰动是为缓解低位碰撞
桶内查找	链表长度 = 全部条目 → O(n)	泊松分布假设被破坏
树化	表长不足 64 时先 `resize()`，不树化；且 `Comparable` 缺失时只能用 `tieBreakOrder`	树化要求键可比较才有意义
`equals`/`hashCode` 一致性	放得进取不出（hash 改变）	key 必须不可变

“链表长度到 8 就变红黑树”是错的：binCount >= 8 时若 table.length < 64 会先 resize()；退化阈值是 6，中间留 7 的缓冲避免反复转换。

对症做法：

java

// 1. key 用 record/不可变类，hashCode 覆盖全部 equals 字段
public record RouteKey(String host, String path, int tenantId) {}   // 自动生成正确的 equals/hashCode

// 2. 长字符串 key 做“先粗筛再精比较”，避免整串 hash 开销集中在同前缀
//    例：path 的分布极集中时，把 tenant + host 也纳入 hash，让分布打散

// 3. 结构可验证：把“单桶最大长度”做成指标，测试里直接断言
@Test void hashDistributesAcrossBuckets() {
    Map<RouteKey, Handler> m = new HashMap<>(65536);
    for (int i = 0; i < 50_000; i++) m.put(key(i), h);
    assertThat(maxBucketLength(m)).isLessThanOrEqualTo(8);
}

text

4. 热路径上的“取不到再回源”要检查 key 是否等价：
   两边 hashCode 实现对不齐时，缓存命中率低但无异常，最难定位。
5. key 可变是另一类静默失效：
   放进 map 后修改参与 hashCode 的字段，元素会“查不到但也删不掉”，
   最终表现为内存缓慢增长。

复盘要点：判据是“所有自定义 map key 都是 record 或有生成的 equals/hashCode”+“单桶最大长度有测试断言”。命中率指标同样能暴露这类问题：缓存命中率异常低而键空间不大时，先查 hashCode 分布，而不是先怀疑容量。0.75 是时间与空间的折中，不是泊松分布推出来的——它解释的是“为什么 8 很少发生”，别反过来用它当容量依据。

最小上手

用两个线程并发累加，验证 merge 的原子性：

java

import java.util.concurrent.*;

public class ChmDemo {
    public static void main(String[] args) throws Exception {
        ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
        Runnable add = () -> {
            for (int i = 0; i < 1000; i++) {
                map.merge("count", 1, Integer::sum);
            }
        };
        Thread a = new Thread(add);
        Thread b = new Thread(add);
        a.start(); b.start();
        a.join(); b.join();
        System.out.println(map.get("count")); // 2000
        System.out.println(map.mappingCount());
    }
}

bash

javac ChmDemo.java && java ChmDemo
# 输出 2000 和 1

如果换成 map.put("count", map.getOrDefault("count", 0) + 1)，两个线程会互相覆盖，最终小于 2000。

生产动作

预估容量：new HashMap<>((int)(expected / 0.75f) + 1)，避免反复扩容；CHM 的初始容量也会按负载因子换算，首次插入才真正建表。
key 必须不可变：hashCode/equals 依赖的字段在放入后不能改，否则桶下标变了，get 找不到；优先用 String、Integer、record 或不可变值对象。
复合操作要原子：CHM 的 get 和 put 各自线程安全，但「先查再改」不是；用 compute、merge、computeIfAbsent，并且 mapping function 要短，不要在里面修改同一个 map。
不要用 Collections.synchronizedMap 替代 CHM：它锁整张表，读也串行；CHM 的读基本无锁。
排查：jcmd <pid> GC.class_histogram 看 HashMap$Node、ConcurrentHashMap$Node 数量和占用；堆 dump 里按 Dominator Tree 找超大的 map，再查业务缓存是否无界。
并发测试：用 jcstress 或压力测试验证复合操作；单线程单元测试发现不了丢失更新。

边界

CHM 不是强一致：迭代器是弱一致的，size() 不精确，跨 key 的操作没有事务语义。
树化不是安全的万能药：它能缓解碰撞，但不能阻止攻击者构造大量同 hash 的 key；对外部输入仍要限制大小和来源。
HashMap 在 JDK 8 仍不安全：没有死循环不代表没有数据覆盖；多线程共享写必须用 CHM 或外部同步。
CHM 不允许 null：需要表达「没有值」时用 Optional、哨兵对象或 containsKey，不要试图绕过。
红黑树有额外开销：节点从 Node 变成 TreeNode，占用更大；正常哈希分布下几乎不会触发，不要为了「优化」手动调低树化阈值。

讲清楚

HashMap 是数组加链表，冲突多时转红黑树。树化要同时满足桶内节点数达到 8 和表容量至少 64；容量不够时先扩容，所以「到 8 就树化」不准确。0.75 是空间和冲突的折中，泊松分布只说明 8 这个阈值很少被触发，不是 0.75 的推导。
扩容时 JDK 8 按 hash 的新高位把链表拆成两条，避免重新计算 hash；JDK 7 的头插法在并发扩容时会成环，JDK 8 修了环但仍会丢数据。ConcurrentHashMap 用 CAS 插空桶、synchronized 锁桶头、ForwardingNode 协助扩容，读不加锁，代价是弱一致性和禁止 null。生产上最重要的是不可变 key、预估容量、用 compute/merge 表达原子复合操作。

计算机原理

Go

Python 语言

Linux

Java

HashMap 与 ConcurrentHashMap

为什么需要

核心机制

HashMap 的数据结构

树化的真实条件

扩容与迁移

ConcurrentHashMap 的并发写入

实战场景

一、并发写 `HashMap`，缓存里凭空少了一半数据

二、`containsKey` + `put` 不是原子，客户端被初始化三次

三、自定义 key 的 `hashCode` 返回常量，get 变成线性扫描

最小上手

生产动作

边界

讲清楚

HashMap 与 ConcurrentHashMap ​

为什么需要 ​

核心机制 ​

HashMap 的数据结构 ​

树化的真实条件 ​

扩容与迁移 ​

ConcurrentHashMap 的并发写入 ​

实战场景 ​

一、并发写 HashMap，缓存里凭空少了一半数据 ​

二、containsKey + put 不是原子，客户端被初始化三次 ​

三、自定义 key 的 hashCode 返回常量，get 变成线性扫描 ​

最小上手 ​

生产动作 ​

边界 ​

讲清楚 ​

HashMap 与 ConcurrentHashMap

为什么需要

核心机制

HashMap 的数据结构

树化的真实条件

扩容与迁移

ConcurrentHashMap 的并发写入

实战场景

一、并发写 `HashMap`，缓存里凭空少了一半数据

二、`containsKey` + `put` 不是原子，客户端被初始化三次

三、自定义 key 的 `hashCode` 返回常量，get 变成线性扫描

最小上手

生产动作

边界

讲清楚