Java HashMap与ConcurrentHashMap详解
·
HashMap 与 ConcurrentHashMap 详解 — 面试再也不怕问并发Map了
🧑💻 作者：没有逆称
💡 前言：HashMap 和 ConcurrentHashMap 是 Java 面试的高频考点，尤其是 ConcurrentHashMap 的并发原理，JDK 7 和 JDK 8 的区别，扩容机制等。本文从数据结构开始讲起，逐步深入到并发原理，力求把每个细节都讲清楚。
📌 文章目录
- 一、HashMap 基础 — 底层数据结构
- 二、HashMap 的哈希冲突解决 — 拉链法与红黑树
- 三、HashMap 扩容机制 — 为什么要翻倍？
- 四、HashMap 线程不安全的表现
- 五、ConcurrentHashMap 登场 — 解决并发问题
- 六、JDK 7 vs JDK 8 — ConcurrentHashMap 的演进
- 七、JDK 8 ConcurrentHashMap 核心原理
- 八、面试高频问题整理
- 九、使用场景总结与选型建议
一、HashMap 基础 — 底层数据结构
1.1 数组 + 链表 = HashMap？
HashMap 的底层是**数组（桶）+ 链表（解决哈希冲突）**的结构：
HashMap 内部结构
┌─────────────────────────────────────────────────────┐
│ Node<K,V>[] table（数组，每个元素叫桶） │
├─────────────────────────────────────────────────────┤
│ index 0 │ index 1 │ index 2 │ index 3 │ ... │
│ ▼ ▼ ▼ ▼ │
│ [链表头] [链表头] [链表头] [链表头] │
│ │ │ │ │ │
│ ▼ ▼ ▼ ▼ │
│ 下一个节点 null 下一个节点 下一个节点 │
└─────────────────────────────────────────────────────┘
基本原理：
put(key, value)时，先用hash(key)计算哈希值- 根据
hash % table.length（或hash & (length - 1)）算出数组下标 - 把
key-value封装成 Node 放到对应位置的链表头
为什么用 & 运算而不是 %？
// 取模运算
index = hash % table.length; // 较慢
// 位运算（JDK 用这个）
index = hash & (table.length - 1); // 快得多，要求 length 是 2 的幂次
1.2 hash() 方法 — 扰动函数
JDK 7 和 JDK 8 的 hash 实现略有不同，JDK 8 做了优化：
// JDK 8 的 hash 实现
static final int hash(Object key) {
int h;
// key.hashCode() 的高 16 位和低 16 位异或，保留更多哈希特征
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 计算数组下标
index = (table.length - 1) & hash(key);
为什么要扰动？
key.hashCode() 返回的 32 位 int 值，如果只用低几位做下标，高位信息就浪费了。异或高 16 位可以让哈希值分布更均匀，减少哈希冲突。
原始 hashCode： 11111111 11111111 11111111 11001010
▼
扰动后 hash： 11111111 11111111 11001010 10111100
↑
高16位与低16位异或
1.3 关键参数
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
// 默认初始容量（必须是 2 的幂次）
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;
// 链表转红黑树的阈值（JDK 8 新增）
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 最小树形化容量阈值
static final int MIN_TREEIFY_CAPACITY = 64;
}
| 参数 | 默认值 | 说明 |
|---|---|---|
initialCapacity |
16 | 初始桶数组大小 |
loadFactor |
0.75 | 负载因子，决定何时扩容 |
threshold |
capacity × loadFactor |
触发扩容的阈值（默认 12） |
💡 负载因子 0.75 的选择：空间利用率和哈希冲突概率的平衡。太高 → 冲突多、链表长；太低 → 空间浪费、扩容频繁。
二、HashMap 的哈希冲突解决 — 拉链法与红黑树
2.1 什么是哈希冲突？
两个不同的 key，算出来的数组下标相同，就是哈希冲突。
// 假设 table.length = 16
hash("张三") & 15 = 5
hash("李四") & 15 = 5 // 冲突！
2.2 拉链法（Separate Chaining）
把冲突的元素用链表串起来：
// Node 节点结构
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; // 指向下一个节点的指针
}
index = 5 的桶：
Node("张三", 1) → Node("李四", 2) → null
JDK 7 vs JDK 8 链表插入顺序：
- JDK 7：头插法（新元素插到链表头）→
new Node.next = oldHead - JDK 8：尾插法（新元素插到链表尾）→ 遍历到尾部追加
⚠️ JDK 7 头插法有个严重问题：并发下扩容时，可能形成环形链表，导致死循环。JDK 8 改成尾插法解决了这个问题。
2.3 红黑树优化（JDK 8 新增）
当链表长度超过 8 时，链表会转换成红黑树：
链表长度 ≤ 8 → 链表（O(n) 查找）
链表长度 > 8 → 红黑树（O(log n) 查找）
红黑树节点数 ≤ 6 → 退化为链表
为什么选 8 而不是其他数字？
源码注释里有说明：哈希碰撞服从泊松分布，链表长度达到 8 的概率只有 0.00000006（千万分之六）。换句话说，8 是一个非常极端的情况，正常业务几乎不会触发红黑树。但如果真的触发了，说明哈希函数设计有问题。
三、HashMap 扩容机制 — 为什么要翻倍？
3.1 扩容时机
当 size（元素个数） > threshold（capacity × loadFactor） 时，触发扩容：
// put() 里的扩容判断
if (++size > threshold) {
resize(2 * table.length); // 容量翻倍
}
举个例子：
- 初始
capacity = 16，loadFactor = 0.75 threshold = 12- 放入第 13 个元素时，触发扩容 →
capacity = 32，threshold = 24
3.2 扩容过程
扩容前：capacity = 16
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
扩容后：capacity = 32（翻倍）
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
3.3 重新计算下标 — 为什么容量必须 2 的幂次？
这是面试常考的点。扩容后重新计算下标，不需要重新 hash，可以直接用新增的那位判断：
// 原容量 oldCap = 16，二进制 10000
// 新容量 newCap = 32，二进制 100000
// 原下标 = hash & (oldCap - 1) = hash & 01111
// 新下标有两种可能：
// - hash 第 5 位为 0 → 新下标 = 旧下标
// - hash 第 5 位为 1 → 新下标 = 旧下标 + oldCap
// 举例：
// hash = 27 (二进制 11011)
// oldCap - 1 = 15 (二进制 01111)
// 27 & 15 = 11 (旧下标)
// newCap - 1 = 31 (二进制 11111)
// 27 & 31 = 27 (新下标 = 旧下标 + 16)
结论：容量是 2 的幂次时，扩容后只需要检查哈希值新增的那一位是 0 还是 1，就能确定新下标，不用重新算 hash。
四、HashMap 线程不安全的表现
HashMap 不是线程安全的，并发下会出现三个经典问题：
4.1 数据覆盖
// 两个线程同时 put(key, value)，同一个桶的位置
// 线程A：计算下标为 3
// 线程B：计算下标也为 3
// 结果：后写的覆盖先写的，数据丢失
4.2 死循环（JDK 7 头插法）
JDK 7 在并发扩容时，链表头插法可能导致环形链表，get() 时死循环：
JDK 7 扩容时的死循环形成过程：
原链表：A → B → C
线程A扩容：A → B → C（还没复制完）
线程B也扩容：同时操作同一个桶
↓
A.next = B
B.next = A ← 形成环形链表！
↓
遍历 get() 时：A → B → A → B → ... 死循环，CPU 100%
JDK 8 改用尾插法解决了这个问题，但仍然不是线程安全的。
4.3 并发场景下不要用 HashMap
| 场景 | 推荐方案 |
|---|---|
| 并发度低，不需要锁 | Collections.synchronizedMap(new HashMap<>()) |
| 并发读为主 | ConcurrentHashMap |
| 需要原子操作（increment） | ConcurrentHashMap + compute() 等方法 |
| 读远多于写，写需要原子操作 | ConcurrentSkipListMap（跳表，有序） |
五、ConcurrentHashMap 登场 — 解决并发问题
5.1 为什么不用 synchronized 包装 HashMap？
Collections.synchronizedMap() 给整个 Map 加了一把全局锁，任何操作都要竞争同一把锁：
// synchronizedMap 底层就是 synchronized 包裹每个方法
public synchronized V get(Object key) { ... }
public synchronized V put(K key, V value) { ... }
问题：同一时刻只能有一个线程操作 Map，其他线程全部阻塞，并发性能极差。
5.2 核心思想：分段锁
ConcurrentHashMap 的核心思路是把锁粒度拆细，让不同线程操作不同桶时互不影响。
六、JDK 7 vs JDK 8 — ConcurrentHashMap 的演进
6.1 JDK 7：Segment 分段锁
ConcurrentHashMap
│
├── Segment[0]（锁1）→ 桶0-15
├── Segment[1]（锁2）→ 桶16-31
├── Segment[2]（锁3）→ 桶32-47
└── ...
- 默认 16 个 Segment（可配置）
- 每个 Segment 持有一把锁
- 不同 Segment 之间完全并发
// JDK 7 底层结构
public class ConcurrentHashMap<K,V> {
// Segment 数组，继承了 ReentrantLock
final Segment<K,V>[] segments;
static final class Segment<K,V> extends ReentrantLock {
transient volatile HashEntry<K,V>[] table;
}
}
优点：分段锁，并发度高
缺点：Segment 数量固定，扩容只发生在 Segment 内部，且不能全局扩容
6.2 JDK 8：去掉 Segment，改为 synchronized + CAS
JDK 8 做了翻天覆地的改变：
JDK 8 ConcurrentHashMap
│
├── 去掉 Segment
├── 桶数组：Node<K,V>[]
├── 每个桶单独加锁（synchronized）
├── 用 CAS 保证并发安全
└── 链表 > 8 → 红黑树（JDK 8 新增）
为什么 JDK 8 要改？
- Segment 分段锁数量固定（默认 16），当数据集中在某一个段时，该段压力依然很大
- JDK 6 引入了偏向锁、轻量级锁优化，
synchronized性能大幅提升，不再是"重量级锁"的代名词 - 红黑树的引入让查询复杂度从 O(n) 降到 O(log n)
七、JDK 8 ConcurrentHashMap 核心原理
7.1 数据结构
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
implements ConcurrentMap<K,V>, Serializable {
// 底层数组（volatile，保证可见性）
transient volatile Node<K,V>[] table;
// 控制并发的基础变量
private transient volatile int sizeCtl;
}
Node 结构：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V value; // value 用 volatile，保证可见性
volatile Node<K,V> next; // 链表指针
}
7.2 put() 流程
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode()); // 和 HashMap 一样的扰动函数
int binCount = 0; // 当前桶的链表长度
// 自旋 + CAS
for (Node<K,V>[] tab = table;;) {
Node<K,V> f;
int n, i, fh;
// 1. 数组未初始化 → CAS 初始化数组
if (tab == null || (n = tab.length) == 0) {
tab = initTable();
}
// 2. 桶为空 → CAS 放入新节点（无锁操作）
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) {
break;
}
}
// 3. 桶有值 → synchronized 锁住桶，处理链表/红黑树
else {
synchronized (f) { // 只锁当前桶，不影响其他桶
// 检查 f 是否还是原节点（可能其他线程已修改）
if (tabAt(tab, i) != f) continue;
// 链表插入
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
if (e.hash == hash && (ek = e.key) == key || (ek != null && ek.equals(key)))) {
V oldVal = e.value;
if (!onlyIfAbsent) e.value = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key, value, null);
break;
}
}
}
// 红黑树插入
else if (f instanceof TreeBin) {
TreeBin<K,V> t = (TreeBin<K,V>) f;
// 红黑树插入（putTreeVal）
}
}
// 链表长度 > 8 → 转红黑树
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD) {
treeifyBin(tab, i);
}
if (alreadyLocked) return oldValue;
return null;
}
}
}
// 更新计数器
addCount(1L, binCount);
return null;
}
put() 流程总结：
put(key, value)
│
├── 数组未初始化？ → CAS 初始化（多线程竞争，只有一个人成功）
│
├── 桶为空？ → CAS 直接放（无锁，true）
│
└── 桶不为空？ → synchronized 锁住这个桶
│
├── 链表模式 → 遍历找到则覆盖，没找到则尾插
├── 红黑树模式 → 红黑树插入
│
└── 链表长度 > 8 → 转红黑树
7.3 并发读 — 不加锁怎么保证线程安全？
ConcurrentHashMap 的读操作完全不加锁：
public V get(Object key) {
Node<K,V>[] tab;
Node<K,V> e, p;
int n, eh;
K ek;
// 1. 计算 hash
int h = spread(key.hashCode());
// 2. 数组已初始化 && 桶不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// 3. 第一个节点就是 → 直接返回
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && ek.equals(key))) {
return e.value;
}
}
// 4. eh < 0 说明是红黑树，用 treeFind 查找
else if (eh < 0) {
return (p = e.find(h, key)) != null ? p.value : null;
}
// 5. 链表模式 → 遍历查找
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && ek.equals(key)))) {
return e.value;
}
}
}
return null;
}
读不加锁的原因：
value是volatile的 → 每次读取都是主内存最新值Node.next也是volatile的 → 链表结构变化能感知到
7.4 扩容机制 — 多线程并发扩容
ConcurrentHashMap 的扩容是多线程并发的，这是它性能强大的关键：
// 核心扩容方法：transfer()
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// 每个线程负责一段桶的迁移
// MIN_TRANSFER_STRIDE = 16，最小迁移单位
stride = (n >>> 3) / NCPU; // 按 CPU 核数分配
if (stride < MIN_TRANSFER_STRIDE) stride = MIN_TRANSFER_STRIDE;
// 第一个线程会初始化新数组 nextTab
if (nextTab == null) {
nextTab = (Node<K,V>[]) new Node<?,?>[n << 1];
nextTable = nextTab;
transferIndex = n;
}
// 线程池并发迁移
for (int i = 0; i < n; i += stride) {
// 每个线程 CAS 抢任务（领自己负责的桶区间）
// 然后把旧桶节点拆分到新数组两个位置
}
}
扩容原理：
旧数组 capacity = 16 新数组 capacity = 32
┌──┬──┬──┬──┬──┬──┬──┬──┐ ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
│A │B │C │D │E │F │G │H │ │A │ │B │ │C │ │D │ │E │ │F │ │G │ │H │ │
└──┴──┴──┴──┴──┴──┴──┴──┘ └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
重新计算下标：hash & (newCap - 1)
hash 第 5 位为 0 → 原位置
hash 第 5 位为 1 → 原位置 + oldCap
多线程扩容的关键：
- 多个线程各自领一段桶迁移，互相不影响
transferIndex从后往前分配（避免重复）sizeCtl记录参与扩容的线程数
八、面试高频问题整理
Q1：HashMap 和 ConcurrentHashMap 的区别？
| 维度 | HashMap | ConcurrentHashMap |
|---|---|---|
| 线程安全 | ❌ 不安全 | ✅ 安全 |
| 锁粒度 | 无 | JDK 7：Segment 分段锁；JDK 8：桶级锁 |
| 并发读 | — | ✅ 读操作不加锁（volatile） |
| 数据结构 | 数组+链表+红黑树 | 同 HashMap |
| null 支持 | key/value 都可以为 null | key/value 都不能为 null |
| 性能 | 单线程场景高 | 多线程场景高 |
| 底层实现 | 数组+链表（单向链表） | CAS + synchronized + volatile |
Q2：ConcurrentHashMap 在 JDK 7 和 JDK 8 的区别？
| 维度 | JDK 7 | JDK 8 |
|---|---|---|
| 数据结构 | Segment + HashEntry（数组+链表） | Node[] + 链表/红黑树 |
| 并发方式 | Segment 分段锁（默认16个） | synchronized 锁桶 + CAS |
| 锁粒度 | Segment 级别（较粗） | 桶级别（更细） |
| 并发扩容 | 不支持 | 支持多线程并发扩容 |
| 红黑树 | ❌ 不支持 | ✅ 支持（链表长度 > 8） |
| 查询复杂度 | 最坏 O(n) | 链表 O(n)，红黑树 O(log n) |
Q3：ConcurrentHashMap 的 size() 是怎么计算的？
JDK 7 用 Segment 分别维护各自的计数，求和得到总数。JDK 8 改成了 baseCount + CounterCell[]：
// JDK 8 的计数机制：
// 每次 put 成功，CAS 尝试给 baseCount + 1
// 如果 CAS 失败（并发竞争），则放到 CounterCell 数组中各自分别计数
// 查询 size 时：baseCount + sum(CounterCell[])
private transient volatile long baseCount;
private transient volatile CounterCell[] counterCells;
// put() 时调用
final long sumCount() {
long sum = baseCount;
for (CounterCell cell : counterCells) {
sum += cell.value;
}
return sum;
}
为什么不用一个 AtomicLong？ 因为高并发下 CAS 竞争激烈，容易失败重试。CounterCell 数组分散计数，减少竞争。
Q4：put() 时，如果发现正在扩容怎么办？
// JDK 8 的处理：帮助扩容（Helper Thread）
else if ((fh = f.hash) == MOVED) {
// MOVED = -1，表示正在扩容
// 当前线程去帮助扩容，扩容完了再继续插入
tab = helpTransfer(tab, f);
}
helpTransfer() 会让当前线程参与扩容过程，领一段桶来迁移，而不是干等着。
Q5：ConcurrentHashMap 的 key 和 value 为什么不能为 null？
HashMap 允许 key == null，因为单线程下可以区分"找不到 key"和"key 对应的 value 是 null"。
ConcurrentHashMap 是多线程的，无法区分：
- 线程 A 读取
key，发现value == null→ 到底是 value 本来就是 null，还是 key 不存在？ - 如果 key 不存在，另一个线程可能正在 put
所以直接禁止 null，避免歧义。这也是它和 Hashtable 少有的共同点。
Q6：HashMap 的负载因子为什么是 0.75？
源码注释的解释：时间和空间成本的平衡。
假设 capacity = 16，负载因子：
0.5：扩容阈值 = 8，空间利用率低，但哈希冲突少0.75：扩容阈值 = 12，平衡点，泊松分布验证过1.0：扩容阈值 = 16，空间利用率高，但哈希冲突严重，链表变长，查询变慢
0.75 附近时，哈希碰撞次数的期望值最优，查找复杂度接近 O(1)。
九、使用场景总结与选型建议
9.1 什么时候用哪个？
单线程？
│
├── ✅ HashMap（简单高效）
│
└── 多线程？
│
├── 并发读为主，偶尔写？
│ ├── ✅ ConcurrentHashMap（读不加锁）
│ └── 推荐：`new ConcurrentHashMap<>()`
│
├── 需要有序遍历？
│ └── ✅ ConcurrentSkipListMap（跳表，有序）
│
└── 需要锁住整个 Map 操作？
└── ❌ 考虑 Collections.synchronizedMap()
（性能差，一般不推荐）
9.2 总结对比表
| 集合 | 线程安全 | 并发度 | 数据结构 | null 支持 | 适用场景 |
|---|---|---|---|---|---|
| HashMap | ❌ | 单线程 | 数组+链表/红黑树 | key/value 都可 null | 单线程快速查找 |
| Hashtable | ✅ | 低（全表锁） | 数组+链表 | 都不行 | 不推荐 |
| ConcurrentHashMap | ✅ | 高（桶锁） | 数组+链表/红黑树 | 都不行 | 高并发写场景 |
| ConcurrentSkipListMap | ✅ | 高 | 跳表 | 都不行 | 需要有序的高并发场景 |
| Collections.synchronizedMap() | ✅ | 低（全表锁） | 同 HashMap | 都可 null | 不推荐 |
📌 回到目录
- 一、HashMap 基础 — 底层数据结构
- 二、HashMap 的哈希冲突解决 — 拉链法与红黑树
- 三、HashMap 扩容机制 — 为什么要翻倍？
- 四、HashMap 线程不安全的表现
- 五、ConcurrentHashMap 登场 — 解决并发问题
- 六、JDK 7 vs JDK 8 — ConcurrentHashMap 的演进
- 七、JDK 8 ConcurrentHashMap 核心原理
- 八、面试高频问题整理
- 九、使用场景总结与选型建议
参考资料
- Java 官方文档 — ConcurrentHashMap
- 《深入理解 Java 虚拟机》（周志明）— Java 集合框架章节
- JDK 8 源码 ConcurrentHashMap.java
- 美团技术博客：Java 8 系列之重新认识 HashMap
更多推荐
11
0- 0
已为社区贡献4条内容
所有评论(0)