Skip to content

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 并发扩容还可能形成环形链表。

  • 分层要点:

    1. 结构与参数:底层是 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。
    2. put 流程(JDK 8):表为空先 resize();目标桶为空直接放新 Node;桶首节点 key 相等就覆盖;是 TreeNode 走 putTreeVal;否则遍历链表尾插,插入后如果链表长度超过 8,尝试 treeifyBin;最后 ++size,超过阈值再 resize()。get 先用同样方式定位桶,再按 hash 和 equals 比较;containsKey 与 get 类似,但不会返回 value。
    3. 扩容: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,一侧为空直接复用原树。
    4. 树化与退化:TREEIFY_THRESHOLD = 8、UNTREEIFY_THRESHOLD = 6、MIN_TREEIFY_CAPACITY = 64。只有链表长度超过 8(插入第 9 个节点时)且 table 长度至少 64 才真正树化;否则先扩容,因为小表扩容后桶会更分散,避免频繁树化/退化。8 这个阈值来自泊松分布:在 0.75 负载因子下,桶内节点数达到 8 的概率极低;红黑树节点内存约为普通 Node 的两倍,所以用 8/6 的滞回区间避免抖动。
    5. 树化流程(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 的细节见下方流程图。
    6. 并发问题与选型: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 7JDK 8
结构Entry[] + 链表Node[] + 链表 + 红黑树
插入方式头插尾插
哈希定位hashSeed + indexForh ^ (h >>> 16),(n-1) & hash
扩容重新计算下标,头插反转lo/hi 拆分,保持顺序
树化无链表 > 8 且 table >= 64
并发扩容可能形成环,CPU 100%不再成环,但仍会丢数据
初始化首次 put 时 inflateTable首次 put 时 resize(懒分配)
  • 树化 / 拆分关键常量与方法:
名称值 / 作用
TREEIFY_THRESHOLD8;桶内已有 8 个节点、插入第 9 个时尝试树化
UNTREEIFY_THRESHOLD6;split 后某侧 ≤6 退化为链表
MIN_TREEIFY_CAPACITY64;table 小于它时只扩容、不树化
treeifyBin树化入口:先判 64,再把链表节点替换成 TreeNode 并 treeify
TreeNode.treeify按 hash 建树 + balanceInsertion + moveRootToFront
TreeNode.splitresize 时按 oldCap 位拆 lo/hi,必要时重建或退化
  • 追问链:

    1. 为什么容量必须是 2 的幂? → 下标用 (n-1) & hash,只有 n 是 2 的幂时,n-1 才是连续的低位掩码,桶分布才均匀;扩容也能用 hash & oldCap 快速拆分。
    2. 为什么 hash 要异或高 16 位? → n-1 通常只用到低位,高位信息被丢掉;h ^ (h >>> 16) 让高位参与低位运算,减少碰撞。
    3. JDK 8 为什么改尾插? → 头插在并发扩容时可能把链表反过来并形成环;尾插保持顺序,避免这类环,但并没有让 HashMap 变成线程安全。
    4. 为什么链表超过 8 才树化,6 又退化? → TREEIFY_THRESHOLD=8 是阈值,实际在插入第 9 个节点时触发;泊松分布下 8 个节点同桶的概率已经极低;树节点内存更大,8/6 的滞回区间避免在边界反复转换。
    5. 为什么树化还要求 table >= 64? → 表太小时优先扩容,扩容后元素更分散,比立刻建树更划算,也能避免频繁树化/退化。
    6. JDK 8 扩容为什么不用重新 hash? → 容量翻倍后,新下标只多看一位 oldCap:该位为 0 留在原处,为 1 移到 i + oldCap,所以按 lo/hi 拆链即可。
    7. HashMap 线程不安全会怎样? → JDK 7 并发扩容可能成环导致 get 死循环;JDK 8 会丢更新、size 不准、覆盖别人的写入。fail-fast 只能偶尔抛异常,不能当同步手段。
    8. 为什么 HashMap 允许 null key,CHM 不允许? → HashMap 把 null 的 hash 当 0 处理,放在 0 号桶;CHM 的 get 返回 null 无法区分“key 不存在”和“value 为 null”,所以直接禁止 null key/value。
    9. 负载因子 0.75 怎么理解? → 空间和时间的折中:太低浪费数组,太高碰撞变多;0.75 配合泊松分布,让桶长度集中在 0–2 个。一般不改,除非明确做内存/性能取舍。
    10. key 为什么最好用不可变对象? → key 的 hashCode 变了,桶位置就变了,原来的 entry 再也找不到;equals 和 hashCode 必须保持契约一致。
    11. 扩容时红黑树会重新 hash 或重新插入吗? → 不会。split 只按 hash & oldCap 把树节点拆成 lo/hi 两条链,新下标就是 index 或 index + oldCap,不重新计算 hash。
    12. split 后一定还是红黑树吗? → 不一定。任一侧 ≤6 就 untreeify 退化为链表;一侧为空时直接复用原树;只有 lo/hi 都非空才需要重新 treeify。
    13. treeify 时两个 key 的 hash 完全相同怎么办? → 先 comparableClassFor + compareComparables 比较 key;仍相同则 tieBreakOrder:先比类名,再比 System.identityHashCode,保证插入方向确定。
    14. 为什么树化前要先判断 table >= 64? → 小表碰撞多通常是低位不足,先扩容能把节点分散;直接树化成本高,而且很快又要扩容,容易反复树化/退化。
    15. TreeNode 为什么同时维护 next/prev 和 parent/left/right? → 树化后仍要能按链表遍历和 split;next/prev 保桶内顺序,parent/left/right/red 保红黑树结构,退化时再沿 next 变回链表。
  • 生产案例/取舍(示例,替换成你的项目):

    • 单例里用普通 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 没有并发问题。
    • 用 null key 后又在别处假设 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 等实践。