一、基础前置：HashMap（JDK8 为主，对比 JDK7）

1. 核心数据结构

JDK7：数组 + 单向链表

• 底层是 Entry[] 数组，哈希冲突时往后挂单向链表
• 链表过长没有优化，极端情况退化为 O(n) 遍历
• 采用头插法插入新节点

JDK8：数组 + 单向链表 + 红黑树（重点优化）

底层变成了 Node[] table。

哈希寻址

// 扰动函数，高低位异或，减少哈希碰撞
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

用 (table.length - 1) & hash 定位数组下标，替代了取模运算，效率更高。

冲突处理

• 链表节点数 ≥8 且数组长度 ≥64：链表转为红黑树，查询复杂度降到 O(logn)
• 红黑树节点数 ≤6：退化为单向链表，减少维护开销
• 插入方式改为尾插法，规避了并发下循环链表死链问题

2. 关键核心参数

参数	说明
DEFAULT_INITIAL_CAPACITY = 16	默认数组容量，必须是 2 的幂
MAXIMUM_CAPACITY = 1<<30	最大容量
DEFAULT_LOAD_FACTOR = 0.75f	负载因子；元素数量 容量×0.75 触发扩容
TREEIFY_THRESHOLD = 8	链表转红黑树阈值
UNTREEIFY_THRESHOLD = 6	红黑树转回链表阈值

扩容机制（resize）

• 新数组容量为原数组 2 倍，保证依旧是 2 的幂
• 原数组元素重哈希时：
  • hash & oldCap == 0：下标不变
  • hash & oldCap != 0：下标 = 原下标 + 旧容量

不需要重新计算哈希值，仅移位即可，效率大幅提升。

3. 线程安全问题（HashMap 非线程安全）

JDK7 并发扩容致命问题：环形链表 + CPU 100%

多线程同时执行 resize，头插法会导致链表节点互相引用形成闭环。

get() 遍历链表时会死循环。

JDK8 修复了死链，但依旧不安全

1. 并发 put：数据覆盖，两个线程哈希到同一位置，后插入覆盖先插入的数据；
2. 并发扩容：数据丢失；
3. 并发读写会触发 ConcurrentModificationException（迭代器快速失败 fail-fast）。

结论：HashMap 严禁多线程环境直接使用。

4. 常用方法简单流程

put(key,value)

1. key 为 null 固定放在下标 0；
2. 计算 hash，定位数组桶；
3. 桶为空：直接新建 Node 放入；
4. 桶不为空：
   • 首节点 key 相等，直接覆盖 value；
   • 首节点是红黑树节点，调用树的插入逻辑；
   • 遍历链表，找到相同 key 覆盖，遍历结束无重复则尾部新增节点；
5. 插入完成判断是否达到树化阈值；
6. 元素总数 size++，判断是否需要扩容。

get(key)

寻址找到桶后，先判断头节点。

然后进行链表顺序遍历或红黑树查找。

二、ConcurrentHashMap（JDK7 vs JDK8 架构完全重构）

方案背景

解决 HashMap 线程不安全，替代 Hashtable。

Hashtable 采用全局 synchronized 锁整个数组，并发极差。

Hashtable 缺点

所有方法加 synchronized 锁住整张哈希表。

同一时刻只能一个线程读写，高并发下竞争激烈。

1. JDK7 版本：分段锁 Segment + HashEntry

• 整体结构：Segment[] 分段数组，每个 Segment 内部是独立的 HashEntry[] 哈希表
• 分段锁思想：
  • Segment 继承 ReentrantLock，操作某一段哈希表时只锁住当前 Segment
  • 不同 Segment 之间线程可以并发读写，并发粒度大幅缩小
• 默认 16 个 Segment，最多支持 16 个线程并发写入

缺陷

• 分段数量初始化后难以扩容
• 扩容只能单个 Segment 独立扩容
• 查询遍历、size 统计需要遍历所有 Segment 加锁统计，开销大

2. JDK8 重大重构：取消 Segment，CAS + synchronized + 红黑树（主流重点）

整体架构

和 HashMap 结构一致：Node[] + 链表 + 红黑树。

锁粒度细化到数组单个桶（Node 头节点）。

核心保障并发的三大手段

1. CAS 无锁操作：初始化 table、插入空桶节点、计数更新等乐观锁；
2. synchronized 锁桶头节点：同一个哈希桶竞争才加锁，不同桶完全并发，粒度极致细小；
3. volatile 修饰核心变量：table 数组、Node 的 val、next，保证可见性，避免缓存不一致。

关键核心属性

sizeCtl 状态：

• 负数：正在初始化 / 扩容
• 0：数组未初始化
• 正数：下次扩容阈值（容量 ×0.75）

3. 核心方法详解

put () 执行流程

1. key 为空直接抛 NPE（ConcurrentHashMap 不允许 key/value 为 null，HashMap 允许 key 一个 null）；
2. 判断 table 未初始化，CAS 自旋初始化数组；
3. 计算 hash 定位下标 i；
4. table[i] == null：利用 CAS 尝试直接插入新 Node，成功则结束；CAS 失败自旋重试；
5. table[i] != null：
   • 判断当前桶正在扩容（节点是 ForwardingNode），当前线程协助一起扩容；
   • 对桶头 Node 加 synchronized 锁，锁住当前哈希桶：
     1. 链表：遍历覆盖相同 key，无则尾部插入；
     2. 红黑树：树节点插入逻辑；
6. 插入完毕判断链表长度是否树化；
7. addCount() CAS 更新元素总数，检查是否触发扩容。

get () 全程无锁

1. 寻址找到对应桶；
2. 头节点匹配直接返回；
3. 链表遍历 / 红黑树查找。

依靠 volatile 保证节点数据可见性，不加锁，读性能极高。

扩容机制（多线程协助扩容）

1. 单个线程触发扩容后设置 sizeCtl 为扩容标记；
2. 其他线程写入、读取时碰到 ForwardingNode（转发节点），会加入帮忙迁移数据；
3. 多线程分段认领数组下标，并行迁移原数组数据到新数组，大幅提升扩容速度；
4. 迁移完成后切换 table 引用。

size () 统计元素总数

通过 baseCount（基础计数）+ 多个 CounterCell 计数单元，多线程分散计数，减少 CAS 竞争。

• 无竞争时 CAS 更新 baseCount；
• 竞争激烈时线程绑定不同 CounterCell 单独计数，最终累加总和，高性能统计。

4. 为什么不允许 key、value 为 null？

HashMap 允许一个 key=null 放在下标 0。

ConcurrentHashMap 拒绝 null。

并发场景下无法区分：get(key)==null 是key 不存在，还是key 对应 value 本身就是 null。

无锁场景下无法通过二次 containsKey 判断，极易产生并发歧义。

5. 安全机制：fail-safe

迭代器基于快照遍历，不会抛出 ConcurrentModificationException。

迭代期间数据修改能弱感知，不会快速失败。

6. JDK8 锁设计优势对比 JDK7

1. 锁粒度从 Segment 分段 → 单个哈希桶，并发度更高；
2. synchronized 优化：JDK8 偏向锁、轻量级锁、重量级锁自适应，性能优于老版 ReentrantLock；
3. 支持多线程协同扩容，扩容效率更高；
4. 结构和 HashMap 统一，维护成本更低。

三、HashMap vs ConcurrentHashMap 全方位对比

对比维度	HashMap(JDK8)	ConcurrentHashMap(JDK8)
线程安全	不安全，并发丢数据、死循环	安全，CAS+synchronized 保证
锁机制	无锁	CAS + 桶头 synchronized
数据结构	数组 + 链表 + 红黑树	和 HashMap 完全一致
null 值	key 允许 1 个 null，value 允许 null	key、value 都不允许 null
读操作	无锁	无锁，volatile 保证可见性
写并发	完全不支持并发写入	不同桶可并发写入，同桶串行
迭代机制	fail-fast，并发修改抛异常	fail-safe，基于快照不抛异常
适用场景	单线程环境	多线程高并发读写场景
扩容	单线程扩容	多线程协助并行扩容

四、常见面试高频考点梳理

1. 为什么 JDK8 放弃 Segment 分段锁？

1. Segment 占用内存大，初始化开销高；
2. 锁粒度太大，同一 Segment 下不同桶依旧互斥；
3. synchronized 经过 JVM 深度优化，轻量级场景性能优于 ReentrantLock；
4. 细化到桶级锁，并发吞吐量提升明显。

2. put 时什么时候会加锁，什么时候 CAS？

• 桶为空：CAS 无锁插入；
• 桶不为空：锁住桶头节点修改链表 / 红黑树；
• 遇到 ForwardingNode：协助扩容。

3. 负载因子 0.75 的设计原因

平衡哈希冲突概率与空间利用率。

• 过小：频繁扩容，空间浪费；
• 过大：元素拥挤，哈希冲突飙升，链表过长查询变慢；
• 0.75 是统计学上泊松分布最优平衡点。

4. 三种线程安全 Map 选型

1. Hashtable：全局锁，性能极差，废弃不推荐；
2. Collections.synchronizedMap(new HashMap())：方法级 synchronized 锁住整个对象，同一时刻仅一线程读写，适合低并发；
3. ConcurrentHashMap：分段细粒度锁，高并发场景首选。

5. 并发下 HashMap 死循环成因（JDK7）

头插法 + 多线程同时扩容。

新数组迁移时节点引用倒置，两个线程互相引用形成环形链表。

get 无限遍历死循环。

JDK8 尾插法杜绝环形链表，但数据覆盖问题依旧存在。

五、简单使用建议

1. 单线程业务：无脑用 HashMap，性能最优；
2. 多线程频繁读写：ConcurrentHashMap；
3. 只读多写极少：可加 synchronized 包裹 HashMap，简单场景够用；
4. 缓存场景、分布式本地缓存：优先 ConcurrentHashMap。

六、补充经典易错点

1. ConcurrentHashMap 的 size() 是近似值，统计过程中数据还在变更，无法做到绝对精准；
2. computeIfAbsent 这类原子复合操作全程加锁，保证判断 + 赋值原子性；
3. 红黑树只优化长链表查询，短链表遍历开销更低，因此 6 节点回落链表。