定位:面试官问"HashMap的tableSizeFor怎么算""resize时链表为什么用头插法会死循环""ConcurrentHashMap的sizeCtl有几种状态""ForwardingNode是什么",你答不清楚。本节专治这个gap。
默认参数(面试必背):
- DEFAULT_INITIAL_CAPACITY = 16 // 初始容量
- DEFAULT_LOAD_FACTOR = 0.75f // 负载因子
- TREEIFY_THRESHOLD = 8 // 链表转红黑树阈值
- UNTREEIFY_THRESHOLD = 6 // 红黑树退化阈值
- MIN_TREEIFY_CAPACITY = 64 // 转红黑树的最小表容量
- MAXIMUM_CAPACITY = 1 << 30 // 最大容量
为什么负载因子是0.75?
→ 泊松分布下,每个桶超过8个元素的概率仅为0.00000006
→ 太大(1.0):空间利用率高但hash冲突严重
→ 太小(0.5):hash冲突少但空间浪费
→ 0.75是时间和空间的折中
为什么链表转红黑树阈值是8?
→ 遵循泊松分布,正常情况下链表长度超过8的概率极低
→ 如果频繁超过8,应该检查hashCode()的质量
// HashMap 源码:保证容量永远是2的幂
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1; // 最高位1的后1位变为1 → 至少2个连续1
n |= n >>> 2; // 后2位变为1 → 至少4个连续1
n |= n >>> 4; // 后4位变为1 → 至少8个连续1
n |= n >>> 8; // 后8位变为1 → 至少16个连续1
n |= n >>> 16; // 后16位变为1 → 至少32个连续1(int共32位)
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
// 示例:tableSizeFor(13)
// cap - 1 = 12 = 0000 0000 0000 0000 0000 0000 0000 1100
// >>> 1 = 0000...0110, |= → 0000...1110
// >>> 2 = 0000...0011, |= → 0000...1111
// 后续 >>> 4/8/16 不变(已经全是1了)
// n + 1 = 16(2^4)
// 为什么必须是2的幂?
// 因为 hash % capacity 等价于 hash & (capacity - 1)
// 位运算比取模快得多
// HashMap 源码
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 扰动过程:
// hashCode() = 0xABCD1234
// >>> 16 = 0x0000ABCD
// XOR = 0xABCD98F9 (高16位和低16位混合)
//
// 为什么要扰动?
// capacity一般较小(16、32、64...),只有低几位参与定位
// 扰动让高位也参与计算,减少碰撞概率
putVal(key, value) 流程(Java 8):
1. 计算hash = hash(key)
2. 如果table == null || table.length == 0 → resize()
3. 定位桶:(n - 1) & hash
4. 如果桶为空 → 直接放入新Node
5. 如果桶不为空:
5a. 如果首节点key相同(hash相等 && key相等)→ 覆盖value
5b. 如果首节点是TreeNode → 调用红黑树插入
5c. 否则遍历链表:
- 尾插法追加
- 如果链表长度 >= TREEIFY_THRESHOLD - 1 → treeifyBin()
- 如果key已存在 → 覆盖value
6. 如果是覆盖 → 直接返回旧值
7. ++size > threshold → resize()
// Java 8 扩容迁移 —— 拆分 lo/hi 两条链
// 关键:新容量 = 旧容量 * 2
// 每个桶的元素只会迁移到两个位置之一:原位置 或 原位置+旧容量
// 判断方法:(e.hash & oldCap) == 0
// 如果hash在旧容量的那个bit位为0 → 位置不变(lo链)
// 如果为1 → 新位置 = 旧位置 + oldCap(hi链)
/*
* 示例:oldCap = 16 (10000)
* hash1 = 0...01001 → & 10000 = 0 → 桶位置 = 1001 & 1111 = 9(不变)
* hash2 = 1...01001 → & 10000 ≠ 0 → 桶位置 = 1001 + 10000 = 25
*
* 旧表桶9: [Node(hash1)] → [Node(hash2)]
* 新表桶9: [Node(hash1)] (lo链)
* 新表桶25: [Node(hash2)] (hi链)
*/
Java 7 的头插法死循环问题:
Java 7 的 transfer 用头插法(多线程并发resize时):
线程A暂停在 transfer 中间,线程B完成了 transfer
线程A恢复后继续用旧引用做头插法,可能产生环形链表
后续 get() 时 while(e != null) 死循环
Java 8 改为拆分lo/hi两条链 + 尾插法,解决了环形链表问题
但 HashMap 仍然不是线程安全的!并发put可能导致数据丢失
树化条件(两个条件同时满足):
1. 链表长度 >= 8(TREEIFY_THRESHOLD)
2. table.length >= 64(MIN_TREEIFY_CAPACITY)
如果表太小,优先扩容而不是树化
TreeNode vs Node 结构:
┌──────────────────────────────────────┐
│ Node │
│ int hash │
│ K key │
│ V value │
│ Node<K,V> next │
└──────────────────────────────────────┘
┌──────────────────────────────────────┐
│ TreeNode extends Node │
│ TreeNode parent │
│ TreeNode left │
│ TreeNode right │
│ TreeNode prev │ ← 维护双向链表(用于反树化)
│ boolean red │ ← 红黑树节点颜色
└──────────────────────────────────────┘
退化条件:扩容后红黑树节点数 <= 6(UNTREEIFY_THRESHOLD)
CHM Java 8 核心设计:
1. 取消Segment分段锁,改用 CAS + synchronized
2. 锁粒度:每个桶的头节点(Node)
3. 读操作无锁(volatile Node.val / Node.next)
4. 写操作:桶为空用CAS,桶非空用synchronized(头节点)
sizeCtl 状态含义:
┌──────────────┬──────────────────────────────────────────┐
│ sizeCtl 值 │ 含义 │
├──────────────┼──────────────────────────────────────────┤
│ -1 │ 正在初始化 │
│ -(1+n) │ n个线程正在扩容 │
│ 0 │ 未初始化(默认值) │
│ > 0 │ 下次扩容的阈值(capacity * loadFactor) │
└──────────────┴──────────────────────────────────────────┘
ForwardingNode(迁移标记节点):
- hash = -1(MOVED)
- 扩容时,已迁移完成的桶放ForwardingNode
- 其他线程put时遇到ForwardingNode → 帮助扩容(helpTransfer)
┌───────────────┬──────────────┬──────────────┬──────────────┐
│ │ CHM(Java 8) │ syncMap │ Hashtable │
├───────────────┼──────────────┼──────────────┼──────────────┤
│ 锁粒度 │ 桶节点 │ 全表 │ 全表 │
│ 读操作 │ 无锁(volatile)│ synchronized │ synchronized │
│ 写操作 │ CAS+sync │ synchronized │ synchronized │
│ null key/val │ 不允许 │ 允许 │ 不允许 │
│ 迭代器 │ 弱一致 │ 快速失败 │ 枚举 │
│ 并发性能 │ 高 │ 低 │ 低 │
└───────────────┴──────────────┴──────────────┴──────────────┘
结论:CHM完胜,生产环境应始终使用CHM
import java.lang.reflect.Field;
import java.util.HashMap;
/**
* 实验1:验证HashMap内部结构
* 通过反射观察table数组、链表/树结构、容量变化
*/
public class HashMapInspectDemo {
public static void main(String[] args) throws Exception {
HashMap<String, Integer> map = new HashMap<>(4); // 指定初始容量4
// 反射获取table字段
Field tableField = HashMap.class.getDeclaredField("table");
tableField.setAccessible(true);
// 插入元素观察扩容
for (int i = 0; i < 20; i++) {
map.put("key" + i, i);
Object[] table = (Object[]) tableField.get(map);
int capacity = table != null ? table.length : 0;
// 统计每个桶的链表长度
int maxChainLen = 0;
if (table != null) {
for (Object node : table) {
int chainLen = 0;
while (node != null) {
chainLen++;
Field nextField = node.getClass().getDeclaredField("next");
nextField.setAccessible(true);
node = nextField.get(node);
}
maxChainLen = Math.max(maxChainLen, chainLen);
}
}
System.out.printf("size=%2d, capacity=%2d, maxChain=%d%n",
map.size(), capacity, maxChainLen);
}
}
}
import java.util.HashMap;
import java.util.Map;
/**
* 实验2:制造hash冲突,观察链表转红黑树
* 关键:需要构造hash相同但key不同的对象
*/
public class HashMapTreeifyDemo {
// 故意让所有对象的hashCode返回相同值
static class BadKey {
private final String name;
BadKey(String name) { this.name = name; }
@Override
public int hashCode() { return 1; } // 所有key hash相同
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof BadKey)) return false;
return name.equals(((BadKey) o).name);
}
@Override
public String toString() { return name; }
}
public static void main(String[] args) throws Exception {
Map<BadKey, String> map = new HashMap<>();
// 先确保容量 >= 64(否则优先扩容不树化)
// 默认容量16,负载因子0.75,阈值12
// 需要13个元素触发第一次扩容到32
// 需要25个元素触发第二次扩容到64
for (int i = 0; i < 64; i++) {
map.put(new BadKey("key" + i), "val" + i);
}
System.out.println("size=" + map.size());
System.out.println("此时桶0应该已经树化(链表长度 >= 8 且 capacity >= 64)");
// 反射检查桶0的节点类型
Field tableField = HashMap.class.getDeclaredField("table");
tableField.setAccessible(true);
Object[] table = (Object[]) tableField.get(map);
if (table[1] != null) {
System.out.println("桶1节点类型: " + table[1].getClass().getName());
// TreeNode会显示类似 java.util.HashMap$TreeNode
}
}
}
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;
/**
* 实验3:HashMap vs CHM vs synchronizedMap 并发安全性与性能对比
*
* 验证点:
* 1. HashMap并发put可能丢失数据(size不一致)
* 2. CHM并发安全且性能最优
* 3. synchronizedMap安全但性能差
*
* 典型运行结果(16线程,每线程10万次put):
* HashMap: size=1345210 (期望1600000) [LOST] 耗时300ms
* synchronizedMap: size=1600000 [OK] 耗时800ms
* CHM: size=1600000 [OK] 耗时400ms
*/
public class MapConcurrentTest {
static final int THREADS = 16;
static final int OPS_PER_THREAD = 100_000;
public static void main(String[] args) throws Exception {
System.out.println("===== 并发安全性与性能测试 =====\n");
// 测试1:HashMap(不安全,数据可能丢失)
System.out.println("--- HashMap(不安全)---");
testMap(new HashMap<>(), "HashMap");
// 测试2:Collections.synchronizedMap
System.out.println("--- synchronizedMap ---");
testMap(Collections.synchronizedMap(new HashMap<>()), "synchronizedMap");
// 测试3:ConcurrentHashMap
System.out.println("--- ConcurrentHashMap ---");
testMap(new ConcurrentHashMap<>(), "CHM");
// 测试4:CHM 读写并发
System.out.println("--- CHM 高并发写入+读取 ---");
testConcurrentReadWrite();
}
static void testMap(Map<Integer, Integer> map, String name) throws Exception {
CountDownLatch latch = new CountDownLatch(THREADS);
long start = System.currentTimeMillis();
for (int i = 0; i < THREADS; i++) {
final int threadId = i;
new Thread(() -> {
for (int j = 0; j < OPS_PER_THREAD; j++) {
int key = threadId * OPS_PER_THREAD + j;
map.put(key, key);
}
latch.countDown();
}).start();
}
latch.await();
long cost = System.currentTimeMillis() - start;
int expected = THREADS * OPS_PER_THREAD;
int actual = map.size();
String status = (actual == expected) ? "OK" : "LOST " + (expected - actual);
System.out.printf(" %s: size=%d (期望%d) [%s] 耗时%dms%n",
name, actual, expected, status, cost);
}
static void testConcurrentReadWrite() throws Exception {
ConcurrentHashMap<Integer, String> map = new ConcurrentHashMap<>();
AtomicInteger readCount = new AtomicInteger(0);
CountDownLatch latch = new CountDownLatch(THREADS * 2);
// 写线程
for (int i = 0; i < THREADS; i++) {
final int id = i;
new Thread(() -> {
for (int j = 0; j < 10_000; j++) {
map.put(id * 10_000 + j, "val");
}
latch.countDown();
}).start();
}
// 读线程(CHM读无锁)
for (int i = 0; i < THREADS; i++) {
new Thread(() -> {
for (int j = 0; j < 100_000; j++) {
map.get(j % 1000);
readCount.incrementAndGet();
}
latch.countDown();
}).start();
}
long start = System.currentTimeMillis();
latch.await();
long cost = System.currentTimeMillis() - start;
System.out.printf(" CHM 读写并发: 写入%d 读取%d 耗时%dms%n",
map.size(), readCount.get(), cost);
}
}
import java.util.concurrent.ConcurrentHashMap;
import java.lang.reflect.Field;
/**
* 实验4:观察CHM的sizeCtl状态变化
*
* 预期观察:
* 初始 sizeCtl = 0(未初始化)
* 首次put后 sizeCtl = 12(16 * 0.75,下次扩容阈值)
* size超过12后扩容,sizeCtl = 24(32 * 0.75)
*/
public class CHMSizeCtlDemo {
public static void main(String[] args) throws Exception {
ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
Field sizeCtlField = ConcurrentHashMap.class.getDeclaredField("sizeCtl");
sizeCtlField.setAccessible(true);
System.out.println("初始 sizeCtl = " + sizeCtlField.get(map));
for (int i = 0; i < 30; i++) {
map.put("key" + i, "val" + i);
System.out.printf("size=%2d, sizeCtl=%d%n",
map.size(), sizeCtlField.get(map));
}
}
}
Q1.1: Java 7和Java 8有什么区别?
→ Java 7: 数组 + 链表(头插法)
→ Java 8: 数组 + 链表 + 红黑树(尾插法)
→ 树化条件: 链表长度>=8 且 数组长度>=64
Q1.2: 为什么Java 8改为尾插法?
→ Java 7头插法在多线程并发resize时可能产生环形链表(死循环)
→ 尾插法保持了链表的相对顺序,避免了环形链表
→ 但HashMap仍然不是线程安全的(并发put会丢数据)
Q1.3: 红黑树和链表什么时候互相转换?
→ 链表→红黑树: 链表长度>=8 且 数组长度>=64(否则优先扩容)
→ 红黑树→链表: 扩容后树节点数<=6
→ 为什么阈值不同(8和6)?避免频繁转换(中间态7)
Q2.1: 扩容时元素怎么重新分布?
→ 不需要重新计算hash
→ 每个元素只有两种去向:原位置 或 原位置+旧容量
→ 判断条件:(e.hash & oldCap) == 0
→ Java 8拆分为lo/hi两条链,一次性迁移
Q2.2: 为什么容量必须是2的幂?
→ (n-1) & hash 等价于 hash % n,但位运算快
→ 扩容时只需要看新增的那一位bit是0还是1
→ 保证元素均匀分布
Q2.3: HashMap默认容量是多少?指定11会怎样?
→ 默认16
→ 指定11会被tableSizeFor调整为16(大于等于11的最小2的幂)
Q3.1: Java 7和Java 8的CHM有什么区别?
→ Java 7: Segment分段锁(ReentrantLock),默认16段
→ Java 8: CAS + synchronized,锁粒度细化到每个桶的头节点
→ Java 8并发度从固定16变为等于桶数量
Q3.2: CHM的读操作需要加锁吗?
→ 不需要。Node的val和next是volatile的
→ 读操作直接读取,保证可见性
→ 如果遇到ForwardingNode(hash=-1),会转到新表读取
Q3.3: CHM的size()方法怎么实现的?
→ baseCount + CounterCell[](类似LongAdder的思路)
→ sum = baseCount + 所有CounterCell的value
→ 精确度:非精确(类似LongAdder的sum())
Q4.1: 多线程并发put会发生什么?
→ 数据丢失:两个线程同时判断桶为空,一个覆盖另一个
→ size不准:++size不是原子操作
→ Java 7还可能死循环(头插法环形链表)
Q4.2: 怎么选择线程安全的Map?
→ 高并发读写:ConcurrentHashMap
→ 低并发:Collections.synchronizedMap
→ 只读为主:CopyOnWriteArraySet(数据量小时)
→ 绝对不要用Hashtable
1. HashMap并发死循环 —— Java 7头插法导致环形链表,Java 8改为尾插法但仍不安全
2. CHM不允许null key/value —— HashMap允许,但CHM在并发环境下null有歧义
3. HashMap容量不是传入值 —— tableSizeFor会向上取到最近的2的幂
4. 红黑树不一定在链表长度8时触发 —— 还需要表容量>=64,否则优先扩容
5. 以为指定初始容量就能避免扩容 —— 如果负载因子0.75,容量16最多存12个元素
手写tableSizeFor方法,用二进制打印每一步的结果,验证cap=13->16、cap=17->32、cap=100->128。
写一个程序,16个线程各往HashMap中put 10000个不同的key,最后检查map.size()是否等于160000。换成CHM再试一次,对比结果。
打开JDK源码,阅读ConcurrentHashMap.putVal()方法,标注以下关键步骤:
1. 桶为空时的CAS操作
2. 桶非空时的synchronized锁
3. ForwardingNode的处理
4. treeifyBin的触发条件
基于HashMap + 双向链表实现,要求: