Appearance
2.2-1 HashMap(JDK 7 / 8):扩容、树化、并发问题
所属:02 Java 运行时 / 2.2 集合 分级:A 状态:◐ 初稿 关联:2.2-2、2.2-3、2.2-8、2.4-5
题型:原理
一句话结论:HashMap 是“数组 + 链表/红黑树”的哈希表,用
(n-1) & hash定位桶;JDK 8 用尾插、红黑树和 lo/hi 拆分扩容解决了 JDK 7 的部分问题,但它始终不是线程安全的,并发写会丢更新,JDK 7 并发扩容还可能形成环形链表。分层要点:
- 结构与参数:底层是
Node<K,V>[] table,每个桶挂链表,链表过长转红黑树。默认容量 16、负载因子 0.75,阈值threshold = capacity * loadFactor;容量始终是 2 的幂,构造时用tableSizeFor向上取整,JDK 8 首次put才真正分配数组。hash(key) = (h = key.hashCode()) ^ (h >>> 16),让高 16 位也参与索引;下标是(n - 1) & hash。允许一个 null key(hash 为 0,落在 0 号桶)和多个 null value。 - put 流程(JDK 8):表为空先
resize();目标桶为空直接放新 Node;桶首节点 key 相等就覆盖;是TreeNode走putTreeVal;否则遍历链表尾插,插入后如果链表长度超过 8,尝试treeifyBin;最后++size,超过阈值再resize()。get先用同样方式定位桶,再按 hash 和equals比较;containsKey与get类似,但不会返回 value。 - 扩容:JDK 7 的
transfer会重新计算每个元素的下标,并用头插把链表反转,多线程并发扩容时可能让两个节点互相指向,形成环,之后get死循环、CPU 100%。JDK 8 容量翻倍后,元素的新下标只取决于hash & oldCap:为 0 留在原位置(lo 链),不为 0 移到i + oldCap(hi 链),不需要重新 hash,也保持了链表相对顺序。树桶走TreeNode.split,同样按这一位拆成 lo/hi 两条链并保持顺序;任一侧 ≤6 就untreeify退化为链表,只有 lo/hi 都非空时才重新treeify,一侧为空直接复用原树。 - 树化与退化:
TREEIFY_THRESHOLD = 8、UNTREEIFY_THRESHOLD = 6、MIN_TREEIFY_CAPACITY = 64。只有链表长度超过 8(插入第 9 个节点时)且 table 长度至少 64 才真正树化;否则先扩容,因为小表扩容后桶会更分散,避免频繁树化/退化。8 这个阈值来自泊松分布:在 0.75 负载因子下,桶内节点数达到 8 的概率极低;红黑树节点内存约为普通 Node 的两倍,所以用 8/6 的滞回区间避免抖动。 - 树化流程(JDK 8):
putVal尾插后,binCount >= TREEIFY_THRESHOLD - 1(桶内已有 8 个节点、插入第 9 个)触发treeifyBin;若 table 长度 < 64 只resize()返回,否则把桶内链表节点逐个替换成TreeNode并调用treeify:按 hash 插入,hash 相等时依次用comparableClassFor、compareComparables、tieBreakOrder(类名 →identityHashCode)定序,每插一个节点balanceInsertion,最后moveRootToFront把 root 挪到桶头。split的细节见下方流程图。 - 并发问题与选型:HashMap 的
size、modCount、桶链表都不是并发安全的。JDK 7 并发扩容可能成环;JDK 8 改成尾插后不再成环,但++size、检查再插入、扩容竞争仍会丢更新或让 size 不准;fail-fast的ConcurrentModificationException只是尽力探测,不是并发保证。多线程读写用ConcurrentHashMap;需要整体同步才用Collections.synchronizedMap,但它锁整张表,并发度低。
- 结构与参数:底层是
图/流程:
text
put(key, value)
hash = h ^ (h >>> 16)
i = (n - 1) & hash
├─ table 为空 → resize()
├─ 桶为空 → 直接放 Node
├─ 首节点 key 相等 → 覆盖 value
├─ TreeNode → putTreeVal
└─ 链表 → 尾插
├─ 链表长度 > 8 且 n >= 64 → treeifyBin
└─ ++size > threshold → resize()
resize() 的 lo/hi 拆分(oldCap = 16):
hash & 16 == 0 → lo 链,留在 i
hash & 16 != 0 → hi 链,移到 i + 16
treeifyBin(tab, hash):
n < 64 → resize() 返回(只扩容,不建树)
n >= 64 → 链表节点逐个替换成 TreeNode(重建 prev/next)
→ hd.treeify(tab):
├─ 按 hash 插入;hash 相等 →
│ comparableClassFor → compareComparables → tieBreakOrder
│ (类名 → identityHashCode)
├─ 每插一个节点 balanceInsertion
└─ moveRootToFront:root 挪到桶头,修正 tab[index]
TreeNode.split(map, tab, index, bit = oldCap):
沿 next 遍历原树,按 (hash & oldCap) 分两条链
== 0 → lo 链,留在 index
!= 0 → hi 链,移到 index + oldCap
保持顺序,统计 lc / hc
lc <= 6 → untreeify;否则保留树;hi 侧同理
只有 lo、hi 都非空时才 treeify 重建;一侧为空直接复用原树版本/源码锚点:
- JDK 7:
HashMap.Entry、hashSeed、indexFor、transfer头插。 - JDK 8:
Node、TreeNode、putVal、resize、treeifyBin、TreeNode.treeify、TreeNode.split、putTreeVal、tieBreakOrder、moveRootToFront、untreeify、balanceInsertion;TREEIFY_THRESHOLD=8、UNTREEIFY_THRESHOLD=6、MIN_TREEIFY_CAPACITY=64。 - JDK 17/21:HashMap 主体结构延续 JDK 8,未再引入分段/无锁化。
- JDK 7:
对比表:
| 维度 | JDK 7 | JDK 8 |
|---|---|---|
| 结构 | Entry[] + 链表 | Node[] + 链表 + 红黑树 |
| 插入方式 | 头插 | 尾插 |
| 哈希定位 | hashSeed + indexFor | h ^ (h >>> 16),(n-1) & hash |
| 扩容 | 重新计算下标,头插反转 | lo/hi 拆分,保持顺序 |
| 树化 | 无 | 链表 > 8 且 table >= 64 |
| 并发扩容 | 可能形成环,CPU 100% | 不再成环,但仍会丢数据 |
| 初始化 | 首次 put 时 inflateTable | 首次 put 时 resize(懒分配) |
- 树化 / 拆分关键常量与方法:
| 名称 | 值 / 作用 |
|---|---|
TREEIFY_THRESHOLD | 8;桶内已有 8 个节点、插入第 9 个时尝试树化 |
UNTREEIFY_THRESHOLD | 6;split 后某侧 ≤6 退化为链表 |
MIN_TREEIFY_CAPACITY | 64;table 小于它时只扩容、不树化 |
treeifyBin | 树化入口:先判 64,再把链表节点替换成 TreeNode 并 treeify |
TreeNode.treeify | 按 hash 建树 + balanceInsertion + moveRootToFront |
TreeNode.split | resize 时按 oldCap 位拆 lo/hi,必要时重建或退化 |
追问链:
- 为什么容量必须是 2 的幂? → 下标用
(n-1) & hash,只有 n 是 2 的幂时,n-1才是连续的低位掩码,桶分布才均匀;扩容也能用hash & oldCap快速拆分。 - 为什么 hash 要异或高 16 位? →
n-1通常只用到低位,高位信息被丢掉;h ^ (h >>> 16)让高位参与低位运算,减少碰撞。 - JDK 8 为什么改尾插? → 头插在并发扩容时可能把链表反过来并形成环;尾插保持顺序,避免这类环,但并没有让 HashMap 变成线程安全。
- 为什么链表超过 8 才树化,6 又退化? →
TREEIFY_THRESHOLD=8是阈值,实际在插入第 9 个节点时触发;泊松分布下 8 个节点同桶的概率已经极低;树节点内存更大,8/6 的滞回区间避免在边界反复转换。 - 为什么树化还要求 table >= 64? → 表太小时优先扩容,扩容后元素更分散,比立刻建树更划算,也能避免频繁树化/退化。
- JDK 8 扩容为什么不用重新 hash? → 容量翻倍后,新下标只多看一位
oldCap:该位为 0 留在原处,为 1 移到i + oldCap,所以按 lo/hi 拆链即可。 - HashMap 线程不安全会怎样? → JDK 7 并发扩容可能成环导致
get死循环;JDK 8 会丢更新、size 不准、覆盖别人的写入。fail-fast只能偶尔抛异常,不能当同步手段。 - 为什么 HashMap 允许 null key,CHM 不允许? → HashMap 把 null 的 hash 当 0 处理,放在 0 号桶;CHM 的
get返回 null 无法区分“key 不存在”和“value 为 null”,所以直接禁止 null key/value。 - 负载因子 0.75 怎么理解? → 空间和时间的折中:太低浪费数组,太高碰撞变多;0.75 配合泊松分布,让桶长度集中在 0–2 个。一般不改,除非明确做内存/性能取舍。
- key 为什么最好用不可变对象? → key 的
hashCode变了,桶位置就变了,原来的 entry 再也找不到;equals和hashCode必须保持契约一致。 - 扩容时红黑树会重新 hash 或重新插入吗? → 不会。
split只按hash & oldCap把树节点拆成 lo/hi 两条链,新下标就是index或index + oldCap,不重新计算 hash。 split后一定还是红黑树吗? → 不一定。任一侧 ≤6 就untreeify退化为链表;一侧为空时直接复用原树;只有 lo/hi 都非空才需要重新treeify。- treeify 时两个 key 的 hash 完全相同怎么办? → 先
comparableClassFor+compareComparables比较 key;仍相同则tieBreakOrder:先比类名,再比System.identityHashCode,保证插入方向确定。 - 为什么树化前要先判断 table >= 64? → 小表碰撞多通常是低位不足,先扩容能把节点分散;直接树化成本高,而且很快又要扩容,容易反复树化/退化。
TreeNode为什么同时维护next/prev和parent/left/right? → 树化后仍要能按链表遍历和split;next/prev保桶内顺序,parent/left/right/red保红黑树结构,退化时再沿next变回链表。
- 为什么容量必须是 2 的幂? → 下标用
生产案例/取舍(示例,替换成你的项目):
- 单例里用普通
HashMap做本地缓存,多个请求线程同时put,压测时出现缓存条目丢失、size 比预期小;换成ConcurrentHashMap后问题消失。 - 已知大概 10 万条数据,初始化时用
new HashMap<>(expectedSize / 0.75 + 1)预留容量,避免多次扩容和 rehash;但不要为了“省一次扩容”把容量开得过大,数组本身也占内存。 - 配置快照、只读字典这类“发布后不再修改”的场景,用
HashMap足够;需要在多线程间共享并修改,才升级到 CHM。 - 取舍:HashMap 轻、快、内存省,但没有并发保证;
Collections.synchronizedMap简单但锁整表;CHM 并发度高,但单线程小数据下开销略大。 - 恶意构造相同 hash 的 key(HashDoS):JDK 7 下桶退化为链表,查询从 O(1) 退到 O(n),CPU 可被打满;JDK 8 树化后最坏 O(log n) 有所缓解,但入口仍要限制参数数量和大小。
- 树桶在 7/8 边界频繁 put/remove 会反复树化/退化;8/6 的滞回区间就是为避免这种抖动,容量或 hash 分布有问题时先查根因,不要只调阈值。
- 单例里用普通
易错点:
- 把 HashMap 当线程安全容器用,尤其在单例、静态字段、缓存里。
- 认为“JDK 8 改了尾插,所以 HashMap 并发安全”——只是不再成环,仍会丢数据。
- 认为链表超过 8 就一定树化——table 小于 64 时先扩容。
- 重写
equals却没重写hashCode,或 key 的字段被修改。 - 依赖 HashMap 的迭代顺序,或认为它按插入顺序遍历。
- 初始容量按“元素个数”直接传,忽略负载因子,仍会扩容。
- 把 JDK 7 的“并发成环”结论套到 JDK 8 上,或反过来认为 JDK 8 没有并发问题。
- 用
nullkey 后又在别处假设 key 非空。 - 认为扩容时树节点会逐个重新 put——实际是
split按 oldCap 位拆分。 - 认为
split后必然重建红黑树——一侧为空会复用,≤6 会退化。 - 认为链表一到 8 就树化——实际是插入第 9 个且 table ≥64。
30 秒口述稿:
HashMap 是数组加链表/红黑树,用 hash 的低位定位桶。JDK 7 是头插,并发扩容可能形成环,导致 get 死循环;JDK 8 改成尾插,链表超过 8 且表长至少 64 转红黑树,扩容时按
hash & oldCap拆成 lo/hi 两条链(树桶也一样,≤6 退化为链表),不用重新 hash。默认容量 16、负载因子 0.75,容量保持 2 的幂是为了用(n-1) & hash。它允许一个 null key,但始终不是线程安全的;多线程写要用 ConcurrentHashMap。
- 3 分钟展开顺序:结论 → 数组+链表/树与关键参数 → put 流程和 hash 定位 → JDK 7 扩容成环 → JDK 8 lo/hi 拆分(含树桶 split)→ 树化条件与 8/6 阈值 → treeifyBin/treeify 流程与 tieBreakOrder → 并发问题与选型 → 初始容量、可变 key 等实践。