内容纲要
下面把这份(JDK8 系列里最经典的)HashMap
源码按“结构→流程→细节→陷阱→问答”的顺序拆开讲,读完就能把面试里 90% 的追问顶住。
1. 数据结构与关键常量
- 数组 + 链表/红黑树:
Node<K,V>[] table
为桶数组;同桶冲突最初用单向链表,过长后转为红黑树(TreeNode
)。 - 负载因子:
DEFAULT_LOAD_FACTOR=0.75
;阈值threshold=capacity * loadFactor
,超过即扩容。 -
树化与反树化:
TREEIFY_THRESHOLD=8
:桶内结点数 ≥ 8 时尝试树化;UNTREEIFY_THRESHOLD=6
:桶分裂或删除后 ≤ 6 退回链表;MIN_TREEIFY_CAPACITY=64
:表容量 < 64 时不树化而是优先扩容(更划算)。
- 容量必须是 2 的幂:便于
(n-1) & hash
定位桶下标。
2. 哈希与下标
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- “高位扰动”把高 16 位混到低位,减轻在小表上的碰撞。
- 下标:
index = (n - 1) & hash
(n 为数组长度,2 的幂才能用位与)。
3. put 核心流程(putVal
)
- 懒初始化:第一次插入时
resize()
分配默认 16。 - 定位桶:
i = (n-1) & hash
。 -
三种插入路径:
- 桶为空:直接放头结点;
- 桶为链表:遍历到同 key即覆盖;否则尾插,并统计
binCount
,到阈值后treeifyBin
; - 桶为树:走
TreeNode.putTreeVal
红黑树插入与再平衡。
- 结构变化:
modCount++
,size++
;若size > threshold
,扩容。 - 钩子:
afterNodeInsertion(evict)
给LinkedHashMap
用(LRU 等)。
面试提示:首次插入不会立刻根据初始容量建表,而是懒分配;树化前优先扩容(容量<64)。
4. get 核心流程(getNode
)
- 定位桶→看首结点是否命中→若是树则
getTreeNode
,否则链表逐个equals
。 null
key 特殊:hash(null)=0
,照常走 0 号桶。
5. remove 核心流程(removeNode
)
-
找到目标结点后:
- 链表:前驱指向后继;
- 树:
removeTreeNode
做红黑树删除与再平衡;必要时退树成链表(≤6)。
6. 扩容的“低/高位链”分裂优化(resize
)
-
新容量是旧容量的 2 倍。对于桶里的每个结点,根据
(e.hash & oldCap)
:- =0 → 留在原索引 j(lo 链)
- =1 → 去 j+oldCap(hi 链)
- 不重新算 hash,不改变相对遍历顺序,O(n) 地完成再分布;树桶走
TreeNode.split
,可树可链回落。
7. 红黑树桶(TreeNode
)要点
- 只有桶内是红黑树(按
hash
作为主序,Comparable
作为 tie-breaker)。 - 一致但不强序:当
hash
相等、不可比较时,用tieBreakOrder
(类名 +identityHashCode
)稳定插入次序,保证再平衡一致性。 - 树化/分裂/删除都有退化回链表的通道(≤6)。
8. 迭代器与 fail-fast
modCount
记录结构性修改(增删/扩容),迭代器持有expectedModCount
,不一致即抛ConcurrentModificationException
。- fail-fast 不是强保证:只是尽力发现并快速失败。
9. JDK8 扩展方法
-
getOrDefault/putIfAbsent/compute*/merge/forEach/replaceAll
等都复用同一套“找桶→找结点→插/删/改”的骨架,注意:computeIfAbsent
:只有当 key 缺失或 value 为null
时,才会执行函数并写回;merge
:旧值存在用remappingFunction(old,value)
合并,null
结果等价删除。
10. 与 LinkedHashMap 的关系
HashMap
预留钩子:afterNodeAccess/Insertion/Removal
、replacementNode/replacementTreeNode
,供LinkedHashMap
维护双向链(访问顺序/插入顺序)。
11. 经典陷阱与实战建议
- 并发不安全:多线程 put 导致死循环/丢数据(JDK8 通过尾插已修复早年头插反转问题,但仍不安全)。并发用
ConcurrentHashMap
。 - 初始容量别乱配:预估元素个数
N
,设置capacity = tableSizeFor(ceil(N / loadFactor))
,可减少扩容。 - 大量相同 hash:会树化,最坏仍是 O(log n);但自定义
hashCode/equals
请成对正确实现,否则错桶或查找失败。 - 键可为 null:只允许一个
null
key,值可多个null
。 - 遍历成本 \~ capacity + size:容量太大、负载因子过低时,遍历会慢。
12. 高频追问快速答
-
为什么容量必须是 2 的幂?
便于(n-1)&hash
等价hash % n
且更快;并让高位扰动有效映射到下标低位。 -
为什么树化阈值是 8、退树是 6?
结合泊松分布下碰撞概率与内存开销折中;设置回退滞后(8→6)避免频繁抖动。 -
扩容时为什么能用
e.hash & oldCap
划分高低位链?
因为新容量翻倍,仅最高新增位(oldCap 位)决定元素是否“跨越半程”到j+oldCap
。 -
fail-fast 何时触发?
迭代期间发生结构性修改(非迭代器自身remove
),modCount
改变即抛异常。 -
为什么首次构造只记
threshold
不立刻分配表?
懒初始化降低无用分配;真正put
时才resize()
。
13. 调参与选型清单
- 单线程/读多写少:
HashMap
默认(loadFactor=0.75
)即可。 - 预知规模:
new HashMap(initialCapacity)
,按N/0.75
上取整到 2 的幂。 - 并发:
ConcurrentHashMap
;需要遍历弱一致性即可,别指望 fail-fast。 - 需要顺序:用
LinkedHashMap
(比如 LRU 可重写removeEldestEntry
)。
14. 小结(把流程记成 6 句)
hash()
高位扰动 →(n-1)&hash
定桶;- 空桶插;链表尾插,满 8 尝试树化(表<64 先扩容);
- 同 key 覆盖,结构变动改
modCount/size
; - 超阈值扩容,低/高位链 O(n) 拆分;
- 树桶红黑树插删查,必要时退树;
- 迭代全程校验
modCount
,并发改动 fail-fast。