Java 集合框架与 HashMap 底层学习笔记：为什么面试官总揪着负载因子不放
你写业务代码时天天用 HashMap，put 一个值进去，get 出来，完事。但面试官一问你"负载因子为什么是 0.75"，你答不上来，气氛就尴尬了。今天把这块彻底讲透，从数据结构到扩容，再到并发场景的 ConcurrentHashMap，一条线串下来。
手把手实操：先跑通一个 HashMap 的完整生命周期
先建一个测试类，把 HashMap 的底层行为暴露出来看。你不需要额外依赖，JDK 自带工具就够。
import java.util.HashMap;
import java.util.Map;
public class HashMapDemo {
public static void main(String[] args) throws Exception {
// 初始容量16，负载因子0.75，这是默认值
Map<String, String> map = new HashMap<>();
// 插入第1个元素，观察底层数组变化
map.put("key1", "value1");
// 用反射看底层 table 数组的长度
java.lang.reflect.Field tableField = HashMap.class.getDeclaredField("table");
tableField.setAccessible(true);
Object[] table = (Object[]) tableField.get(map);
System.out.println("插入1个元素后 table 长度: " + (table == null ? 0 : table.length));
// 继续插入，直到触发扩容（16 * 0.75 = 12，第13个元素时扩容）
for (int i = 2; i <= 13; i++) {
map.put("key" + i, "value" + i);
}
table = (Object[]) tableField.get(map);
System.out.println("插入13个元素后 table 长度: " + table.length);
}
}跑一下，你会看到第一次打印 table 长度是 16，第二次是 32。这里有个关键点：HashMap 不是插入第一个元素就初始化数组，而是第一次 put 时才懒加载创建，初始容量 16。你踩过坑没？如果你在构造函数里传了容量 1000，HashMap 不会直接给你 1000 的数组，而是向上取最近的 2 的幂，也就是 1024。为什么？因为哈希值要对数组长度取模，用位运算 (n - 1) & hash 比取模快得多，但前提是长度必须是 2 的幂。
再往下挖一层：为什么是 2 的幂？因为 hash & (n - 1) 能确保结果落在 0 到 n-1 之间，且分布均匀。如果 n 不是 2 的幂，比如 17，那 hash & 16 的结果只有 0 或 16，哈希碰撞会爆炸。JDK 工程师用 tableSizeFor 方法把传进来的容量强制转成 2 的幂，你传 1000，它给你 1024，这个细节面试常考。
看源码及解析：put 方法内部的完整调用链路
打开 HashMap 源码，看 put 方法。JDK 8 以后，put 的流程是这样的：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}hash 方法不是直接返回 key.hashCode()，而是做了扰动：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}为什么要异或高 16 位？因为数组长度通常不大，低位参与运算的只有低几位，高位信息丢失，容易碰撞。把高 16 位异或到低位，让高位信息也参与进来，分布更均匀。这是 JDK 8 的优化，JDK 7 是四次扰动，JDK 8 改成一次，因为树化之后碰撞代价降低了。
再看 putVal 的核心分支：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 冲突了，这里判断是链表还是树
if (p instanceof TreeNode)
((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 遍历链表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // 8
treeifyBin(tab, hash);
break;
}
...
}
}
}
}
关键参数：TREEIFY_THRESHOLD = 8，链表长度达到 8 就转红黑树。为什么是 8？源码注释里写了，遵循泊松分布，负载因子 0.75 下，链表长度到 8 的概率是千万分之六，几乎不可能。真到 8 说明哈希函数有问题，或者恶意攻击（哈希碰撞 DoS），这时候转树把查找从 O(n) 降到 O(log n)。
这里有个坑：链表转树之前，treeifyBin 方法会先检查 table 长度，如果小于 MIN_TREEIFY_CAPACITY = 64，不会转树，而是先扩容。为什么？因为链表长可能是因为容量太小，扩容后重新散列，链表自然就短了。这个顺序搞反了会出问题，面试官会拿这个考你。
扩容机制是另一大考点。resize() 方法里，旧容量翻倍，但元素不是全部重新算 hash，而是看 (e.hash & oldCap) 是不是 0。如果是 0，留在原位；不是 0，移动到 原位置 + oldCap。这个设计省了重算 hash 的开销，JDK 8 的优化。你想想，oldCap 是 16，二进制 10000。位序约定从最低位（最右边）开始数、最低位算第 1 位，所以 16 占的是第 5 位：hash 的这一位是 0 就留在低位区，是 1 就进高位区，正好是原索引加 16。JDK 7 扩容要重新计算 hash 再取模，JDK 8 改成位运算判断，性能提升明显。
验证方法：怎么确认你理解了扩容和树化
跑一个实验：插入 30 个哈希值相同但内容不同的对象，每次 put 后用反射读一次 table，把槽位上的节点类型直接打出来。节点类型是 Node，槽位就是链表；变成 TreeNode，说明已经转树。先定义碰撞类，再写观察器：
import java.util.HashMap;
import java.util.Map;
public class ObserveSlot {
static final int BAD_HASH = 1; // 所有对象都撞到同一个槽位
static class BadHash {
final int value;
BadHash(int value) { this.value = value; }
@Override public int hashCode() { return BAD_HASH; }
@Override public boolean equals(Object o) {
return o instanceof BadHash && ((BadHash) o).value == value;
}
}
public static void main(String[] args) throws Exception {
Map<BadHash, Integer> map = new HashMap<>(); // 默认容量 16
java.lang.reflect.Field tableField =
HashMap.class.getDeclaredField("table");
tableField.setAccessible(true);
for (int i = 1; i <= 30; i++) {
map.put(new BadHash(i), i); // 每插一个，就读一次 table
Object[] table = (Object[]) tableField.get(map);
if (table == null) continue;
int slot = BAD_HASH & (table.length - 1); // 和 put 相同的定位公式
Object head = table[slot];
System.out.printf("第%2d个 容量=%2d 槽位%d 节点类型=%-8s 槽内元素=%d%n",
i, table.length, slot,
head.getClass().getSimpleName(), countSlot(head));
}
}
// Node 和 TreeNode 都保留了 next 指针，顺着 next 数一遍就是槽内元素数
static int countSlot(Object head) throws Exception {
int n = 0;
for (Object cur = head; cur != null; cur = nextField(head).get(cur)) n++;
return n;
}
static java.lang.reflect.Field nextField(Object node) throws Exception {
for (Class<?> c = node.getClass(); c != null; c = c.getSuperclass()) {
try {
java.lang.reflect.Field f = c.getDeclaredField("next");
f.setAccessible(true);
return f;
} catch (NoSuchFieldException ignore) { }
}
return null;
}
}看节点类型的核心就一行：head.getClass().getSimpleName()。如果是 JDK 9 以上，跑之前加 JVM 参数 --add-opens java.base/java.util=ALL-UNNAMED，否则反射打不开 table。跑完，输出是一条很清晰的时间线：
第 1个 容量=16 槽位1 节点类型=Node 槽内元素=1
第 2个 容量=16 槽位1 节点类型=Node 槽内元素=2
...
第 8个 容量=16 槽位1 节点类型=Node 槽内元素=8
第 9个 容量=32 槽位1 节点类型=Node 槽内元素=9
第10个 容量=64 槽位1 节点类型=Node 槽内元素=10
第11个 容量=64 槽位1 节点类型=TreeNode 槽内元素=11
...
三行输出把两个阈值的关系交代清楚了：
- 第 9 个元素插入后，链表已经到 8 个，触发
treeifyBin，但数组只有 16，小于MIN_TREEIFY_CAPACITY = 64，于是先扩容到 32——容量变了，节点类型还是Node。 - 第 10 个元素插入后，
treeifyBin又触发，数组 32 还是不够，再扩容到 64，节点类型依旧是Node。 - 第 11 个元素插入后，数组已经 64，
treeifyBin不再扩容，直接转树，节点类型从Node变成TreeNode。
所以 TREEIFY_THRESHOLD = 8 只是触发检查的门槛，转不转树最终看数组长度够不够 64，顺序永远是先扩容、后转树。这和上面的第一个实验扩容点不同：无碰撞时是 size 超过 12 触发扩容；全碰撞时，是 treeifyBin 发现数组太小主动扩容，来得更早。
退回机制：红黑树什么时候退化成链表
树化不是单行道。JDK 8 给「树化」和「退化」用的是两套不一样的判断，方向并不镜像，这也是面试里最容易讲岔的地方。
先破一个常见误解：UNTREEIFY_THRESHOLD = 6 只在扩容时生效。树化发生在 put 的路上，退化却藏在两个完全不同的时机。
时机一：扩容分裂。 扩容把原来的树桶按 e.hash & oldCap 拆成低位（留原索引）和高位（挪到原索引 + oldCap）两半，拆完各看各的长度：
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD) // 低位节点数 <= 6
tab[index] = loHead.untreeify(map); // 直接退回普通链表
else {
tab[index] = loHead;
if (hiHead != null) loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD) // 高位节点数 <= 6
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null) hiHead.treeify(tab);
}
}
TreeNode 比普通 Node 多出 parent/left/right/prev/red 一组字段，单节点内存接近两倍，可节点太少时 O(log n) 的查找优势根本体现不出来，纯属白花钱，所以拆完发现某一边只剩 6 个以内就当场退回去。注意是每一边单独判断：左边 8 个右边 4 个，左边继续当树、右边退回链表，互不牵连。
时机二：删除节点。 这里没有固定数字，JDK 8 用的是结构性判断——树根太「矮」就退化：
if (root == null
|| (movable
&& (root.right == null
|| (rl = root.left) == null
|| rl.left == null))) {
tab[index] = first.untreeify(map); // 树太小，一把退回链表
return;
}root.right == null、root.left == null、root.left.left == null，翻译过来就是「树塌到只剩两三层的骨架」，红黑树的平衡价值荡然无存。源码注释给 UNTREEIFY_THRESHOLD = 6 的理由是 "at most 6 to mesh with shrinkage detection under removal"——让扩容的 6 和删除时的退化判断彼此衔接。所以删节点不会数到 6 就立刻退，而是等树塌到结构性临界点才退，实测大约落在 5 个。
为什么是 8 和 6，而不是同一个数？ 如果树化和退化共用一条阈值线，元素在临界点附近增增减减，就会反复「树化-退化-树化」，每次都重排结构烧性能。中间留 2 的缓冲带，把临界抖动消化掉。8 是「自然碰撞几乎不可能」的边界（泊松分布下千万分之六），6 是「已经不值得用树」的底线，一头防哈希攻击、一头防内存浪费。
光说还是虚的，用反射把两个方向的退化都拍下来。先复刻扩容分裂：准备两类碰撞对象，hash 取 1 和 65——在容量 64 时都落在槽位 1（1 & 63 == 65 & 63 == 1），扩容到 128 时按第七位分家（位序同前：最低位算第 1 位，64 即二进制 1000000），hash & 64 == 0 的留槽位 1、hash & 64 != 0 的挪到槽位 65。插 8 个低位对象加 4 个高位对象，槽位 1 先树化；再用偶数 Integer 把 size 顶过 48（64 的负载因子阈值）触发扩容。真实输出：
插入 12 个碰撞元素后：容量=64 槽位1 节点类型=TreeNode 槽内元素=12
扩容后：容量=128
低位索引 1 节点类型=TreeNode 槽内元素=8
高位索引 65 节点类型=Node 槽内元素=48 > 6 继续当树，4 <= 6 当场退回链表——同一个树桶拆出的两半，命运完全相反。
删除方向同理，代码和上一节的 ObserveSlot 同款（反射读 table、顺着 next 数槽内元素），只是把插入循环换成先插 30 个同哈希对象、再逐个 remove。真实输出的关键两行：
size= 6 槽位1 节点类型=TreeNode 槽内元素=6
size= 5 槽位1 节点类型=Node 槽内元素=56 个节点时树还在硬撑，删到 5 个，removeTreeNode 的结构性判断触发，一把退回链表。HashMap 完整的阈值故事就是：链表变树看节点数和数组长度（8 和 64），树变链表要么看扩容拆完后某一半是否不超过 6，要么看删除后树是否已经塌了——两头不对称，正是为了避免同一个槽位在两种结构之间来回横跳。
并发场景：ConcurrentHashMap 的 CAS 和 synchronized
HashMap 线程不安全，多线程 put 会丢数据，甚至 JDK 7 下扩容时形成环形链表导致死循环。JDK 8 的 ConcurrentHashMap 怎么解决？
看 putVal 的核心代码：
final V putVal(K key, V value, boolean onlyIfAbsent) {
...
for (Node<K,V>[] tab = table;;) {
if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 空槽位用 CAS 插入，无锁
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
break;
} else if (f.hash == MOVED) {
tab = helpTransfer(tab, f); // 扩容中，帮忙迁移
} else {
synchronized (f) { // 槽位有节点，锁住链表头或树根
... // 插入逻辑和 HashMap 类似
}
}
}
}设计动机很清楚：空槽位用 CAS 无锁插入，冲突时锁单个槽位而不是整个表，粒度细到极致。CAS 全称 compare-and-swap（比较并交换），是一条 CPU 原子指令，三个操作数：V 是要改的内存位置，A 是期望的旧值，B 是新值——执行时先读 V 当前的值，等于 A 才把 V 写成 B，否则什么都不做，失败就在循环里重试，所以它本质是乐观锁，适合冲突少的场景。CAS 有个经典陷阱叫 ABA 问题：线程 1 读到 V = A 后挂起，线程 2 把 V 改成 B 又改回 A，线程 1 醒来再 CAS，发现 V 还是 A，以为没人动过就写进去了，实际上中间已经变过两轮。多数场景（包括 ConcurrentHashMap 的空槽位插入）下 ABA 无害；真要防就用 AtomicStampedReference，在值边上绑一个版本号，每次修改加一，比较时连版本一起比。这里有个权衡：如果冲突特别多，CAS 自旋会浪费 CPU，但 Java 8 的 ConcurrentHashMap 默认场景下冲突不频繁，所以整体性能远好于 JDK 7 的分段锁。
tabAt 和 casTabAt 用 Unsafe 的 volatile 读 + CAS 保证可见性和原子性。方法名会随 JDK 版本变，别记死：JDK 8 是 Unsafe.getObjectVolatile 和 compareAndSwapObject；JDK 9 以后改名，JDK 26 里 tabAt 实际调的是 getReferenceAcquire（内部再走 getReferenceVolatile），casTabAt 调的是 compareAndSetReference，语义完全一样。本文源码逻辑按 JDK 8 讲述、本地实验跑在 JDK 26，你看到自己本机方法名对不上别以为写错了。核心不变：读取 table 数组元素时用 volatile 读，因为数组本身不是 volatile，但元素需要可见性，所以用 Unsafe 方法绕过数组的普通读。
扩容时有个 sizeCtl 字段，负数表示正在初始化或扩容，-1 是初始化，-(1 + n) 表示有 n 个线程在帮忙扩容。transfer 方法里每个线程领一段区间，迁移完再领下一段，这就是 helpTransfer 的协作机制。你想想，如果一个线程迁移整个数组，其他线程全等着，那扩容期间并发度归零。分片迁移让其他线程既能读旧数据，又能帮忙干活，这个设计解决了大 Map 扩容的停顿问题。
面试常追问：ConcurrentHashMap 的 size() 怎么算？JDK 8 用 baseCount 加 CounterCell[] 数组，CAS 更新 baseCount 失败就分散到 CounterCell 里，统计时累加。为什么不用 AtomicLong？因为高并发下 CAS 竞争太激烈，分散到多个 cell 降低冲突。这个和 LongAdder 是同一个思路。
面试速答
HashMap 底层是数组加链表加红黑树，负载因子 0.75 是空间和时间的最优权衡，扩容阈值是容量乘负载因子，扩容时容量翻倍且用位运算判断元素迁移位置。链表长度到 8 且数组长度到 64 才转红黑树，否则先扩容。红黑树退化成链表有两个时机：扩容分裂时某一半节点数不超过 6（UNTREEIFY_THRESHOLD），或删除节点后树结构塌到临界点（结构性判断，实测约 5 个）。ConcurrentHashMap 用 CAS 处理空槽位（CAS 三个操作数 V/A/B、失败重试、注意 ABA 问题）、synchronized 锁链表头处理冲突，扩容时多线程协作迁移。记住关键数字：初始容量 16、负载因子 0.75、树化阈值 8、退化阈值 6、最小树化容量 64、扩容翻倍。
核心收获：HashMap 的每个设计细节都是性能和安全的权衡结果，数字背后有概率论和工程实践支撑。下一步：自己动手写一个 BadHash 类触发树化，再写个多线程插入实验对比 HashMap 和 ConcurrentHashMap 的行为差异，跑通了就真会了。
本文关键词：HashMap底层、负载因子、扩容机制、红黑树、ConcurrentHashMap