概念卡片：HashMap 底层原理

一句话机制

HashMap 底层是「数组 + 链表 + 红黑树」的哈希表：先用哈希函数算出索引定位到数组的桶，冲突时用链表（严重时转红黑树）挂在桶上；扩容时数组长度翻倍并保持 2 的 n 次方。它是 Map 家族的性能标杆，也是理解 ConcurrentHashMap 的前置。

数据结构与哈希

java

// 哈希函数：高 16 位参与异或，减少低位冲突
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
// 计算索引：length 是 2 的 n 次方，等价于 hash % length
hash & (table.length - 1)

组件	作用
数组（table）	哈希表的桶，长度是 2 的 n 次方
链表	解决哈希冲突（拉链法）
红黑树	链表过长时替代，查询 O(n)→O(logn)

为什么数组长度是 2 的 n 次方：length - 1 的二进制低位全 1，hash & (length-1) 时低位保留、分布均匀，碰撞概率小、查询快，且位运算比取模快。

put 流程

计算哈希值 + 索引
桶为空 → 直接放
桶非空 → 遍历找「hash 相同且 key 相同」的节点，找到则覆盖 value
没找到 → 尾插新节点，size++，判断是否扩容

链表转红黑树的两个条件（缺一不可）：

单个链表元素个数 ≥ TREEIFY_THRESHOLD（8）
table 长度 ≥ MIN_TREEIFY_CAPACITY（64）

链表 ≥8 但 table <64 时不树化而是扩容（扩容能摊薄冲突，比树化更省）。

扩容（resize）

触发：第一次 put（构造器不初始化 table）；键值对个数 > threshold（容量 × 0.75 负载因子）；链表 ≥8 但 table <64
1.8 优化：元素新位置「要么不变、要么 = 原索引 + 旧数组容量」（利用 2 的 n 次方特性，只判断 hash 的高一位 bit），不必重新哈希

JDK1.7 → 1.8 的三处优化

项	1.7	1.8
数据结构	数组 + 链表	数组 + 链表 + 红黑树
插入方式	头插法	尾插法
扩容重哈希	每个元素重新算位置	位置不变或 +旧容量

HashMap 线程不安全

版本	问题
1.7	扩容死循环（头插法 transfer 翻转链表，多线程形成环）+ 数据丢失/覆盖
1.8	并发 put 数据覆盖（两个线程同时判断桶为空都插入，或 ++size 竞争）

1.7 死循环根因：transfer() 用头插法迁移链表，链表顺序翻转，多线程并发迁移时形成环形链表，get 时死循环。

常见误解（避坑）

❌ "HashMap 冲突就是挂链表，永远不会退化"。→ 链表过长会树化，但红黑树节点 <6 又会退化回链表（remove 时）。
❌ "链表一超 8 就树化"。→ 还得数组长度 ≥64，否则扩容。
❌ "HashMap 允许 key 为 null 是特殊处理"。→ 哈希函数对 null 返回 0，null 固定放在 index 0 的桶。
❌ "负载因子默认 1"。→ 默认 0.75，是时间与空间的折衷：太小频繁扩容、太大冲突多。

关联