Java源码解析-HashMap

内容纲要

下面把这份(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

  1. 懒初始化:第一次插入时 resize() 分配默认 16。
  2. 定位桶i = (n-1) & hash
  3. 三种插入路径

    • 桶为空:直接放头结点;
    • 桶为链表:遍历到同 key即覆盖;否则尾插,并统计 binCount,到阈值后 treeifyBin
    • 桶为树:走 TreeNode.putTreeVal 红黑树插入与再平衡。
  4. 结构变化modCount++size++;若 size > threshold扩容
  5. 钩子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/RemovalreplacementNode/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. 高频追问快速答

  1. 为什么容量必须是 2 的幂?
    便于 (n-1)&hash 等价 hash % n 且更快;并让高位扰动有效映射到下标低位。

  2. 为什么树化阈值是 8、退树是 6?
    结合泊松分布下碰撞概率与内存开销折中;设置回退滞后(8→6)避免频繁抖动。

  3. 扩容时为什么能用 e.hash & oldCap 划分高低位链?
    因为新容量翻倍,仅最高新增位(oldCap 位)决定元素是否“跨越半程”到 j+oldCap

  4. fail-fast 何时触发?
    迭代期间发生结构性修改(非迭代器自身 remove),modCount 改变即抛异常。

  5. 为什么首次构造只记 threshold 不立刻分配表?
    懒初始化降低无用分配;真正 put 时才 resize()

13. 调参与选型清单

  • 单线程/读多写少:HashMap 默认(loadFactor=0.75)即可。
  • 预知规模:new HashMap(initialCapacity),按 N/0.75 上取整到 2 的幂。
  • 并发:ConcurrentHashMap;需要遍历弱一致性即可,别指望 fail-fast。
  • 需要顺序:用 LinkedHashMap(比如 LRU 可重写 removeEldestEntry)。

14. 小结(把流程记成 6 句)

  1. hash() 高位扰动 → (n-1)&hash 定桶;
  2. 空桶插;链表尾插,满 8 尝试树化(表<64 先扩容);
  3. 同 key 覆盖,结构变动改 modCount/size
  4. 超阈值扩容,低/高位链 O(n) 拆分;
  5. 树桶红黑树插删查,必要时退树;
  6. 迭代全程校验 modCount,并发改动 fail-fast。

Leave a Comment

您的电子邮箱地址不会被公开。 必填项已用*标注

close
arrow_upward