--- title: HashMap 内部机制与 JDK7→JDK8 演进 type: concept domain: java-concurrency tags: [hashmap, jdk8, resize, hash-bitwise, tail-insert, red-black-tree, put-get, concurrency-safety] status: learning created: 2026-10-09 last_reviewed: 2026-10-09 method: code-reading + feynman related_questions: - "HashMap在get和put时经过哪些步骤？" - "HashMap是如何扩容的？" - "JDK1.8中HashMap有哪些改变？" - "HashMap用在并发场景中有什么问题？" - "HashMap、Hashtable和ConcurrentHashMap的区别？" related_knowledge: - ./hash-map-concurrent.md - ./red-black-tree.md anki_cards: 8 interview_rounds: - "2026-10-09-round-1-Q2" - "2026-10-09-round-1-Q4" - "2026-10-09-round-1-Q5" - "2026-10-09-round-1-Q6" - "2026-10-09-round-1-Q7" --- # HashMap 内部机制与 JDK7→JDK8 演进 > 数组+链表+红黑树三件套 + hash 位运算 + 尾插法 + resize 位运算优化—— HashMap 是 Java 集合类里最深入的一块知识，也是面试题的常驻嘉宾。 ## TL;DR（30 秒扫完） - **put 四步**：①`hash(key)=h^(h>>>16)` 高位异或；②`(n-1)&hash` 定位桶；③空桶直放/非空遍历 equals 覆盖或尾插；④链长>8 且容量≥64 转树，size>threshold 扩容 - **resize 位运算**：`e.hash & oldCap` 判断——0 留原位，非 0 搬到 `index+oldCap` - **JDK7→8 七改动**：头插→尾插、引入红黑树、hash 算法改造、resize 位运算、TreeNode 拆分、转树双门槛、新增函数式 API - **并发问题六类**：size 错乱、put 覆盖、get null、迭代 CME、check-then-act、可见性缺失 - **替代首选**：`ConcurrentHashMap`（详见 [`hash-map-concurrent.md`](./hash-map-concurrent.md)） ## 关键结论 - **结论 A**：HashMap 数据结构 = 数组 + 链表 + 红黑树（JDK8 新增树化，解决极端哈希冲突） - **结论 B**：`hash(key) = key.hashCode() ^ (key.hashCode() >>> 16)`——高位异或低位参与运算，减少碰撞 - **结论 C**：JDK8 resize 用 `e.hash & oldCap` 位运算优化，避免全部重新 hash，只判断一个 bit 就决定新位置 - **结论 D**：即使 JDK8 修了头插法环形链表 bug，HashMap 仍非线程安全，并发场景必须用 `ConcurrentHashMap` ## 完整讲解（费曼四步） ### STEP 1 · 概念 HashMap 是"数组 + 链表 + 红黑树"的复合结构：数组是桶，桶内是链表（冲突时挂接），链表过长转红黑树降低查找成本。核心动作是 put（放入）和 get（取出），围绕它们展开的还有扩容 resize 和树化转换。JDK7 到 JDK8 有 7 处关键改动，主要解决长链表查找 O(n)、并发扩容环形链表、扩容效率等问题。 ### STEP 2 · 大白话 > **类比**：HashMap 就像一个多层储物柜。最外层是"柜号"数组（桶），每个柜子里挂着"袋子"（链表），袋子里有多个"钥匙-物品对"。取东西时先按 key 的 hash 值定位到哪个柜号（桶），再从柜子的袋子里翻钥匙找物品。如果某个柜子挂的袋子太长（哈希冲突严重），就把袋子升级成"书架"（红黑树），查找更快。 > **JDK8 的改进**：原来 JDK7 的柜子挂新袋子时用"头插法"（新袋子插到最前面），但两个工人同时扩容时会把链表搅成环——现在改成了"尾插法"（新袋子挂到最后），避免环形；扩容时用位运算判断袋子该留原位还是搬到柜子右边（`index+oldCap`），不用重新算 hash。 ### STEP 3 · 底层 #### put 完整流程（JDK8） ```java public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } // 核心逻辑 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; // ① 空表初始化（容量取 initialCapacity 的 2 的幂） if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // ② 桶定位：(n-1) & hash，因为容量是 2 的幂，等价于取模 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); // 空桶：新建 Node 直接放 else { // ③ 桶非空：遍历 Node e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 头节点命中：覆盖 value else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, hash, key, value); // 树化：走树 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 尾插新节点 if (binCount >= TREEIFY_THRESHOLD - 1) // 链长 ≥ 8 treeifyBin(tab, hash); // 且容量 ≥ 64 才转树 break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; // 遍历中命中：准备覆盖 } } if (e != null) { // 命中覆盖 V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; return oldValue; } } ++modCount; if (++size > threshold) // ④ 扩容检查 resize(); afterNodeInsertion(evict); return null; } ``` **关键常量**： | 常量 | 值 | 含义 | |------|-----|------| | `DEFAULT_INITIAL_CAPACITY` | 16 | 默认初始容量 | | `DEFAULT_LOAD_FACTOR` | 0.75f | 默认负载因子 | | `MAXIMUM_CAPACITY` | `1 << 30` | 最大容量 | | `TREEIFY_THRESHOLD` | 8 | 链长转树阈值 | | `UNTREEIFY_THRESHOLD` | 6 | 树退化回链表阈值 | | `MIN_TREEIFY_CAPACITY` | 64 | 转树所需最小桶数 | #### get 完整流程 ```java public V get(Object key) { return getNode(hash(key), key); } final Node getNode(int hash, Object key) { Node[] tab; Node first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) return first; // ① 头节点命中 if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode)first).getTreeNode(hash, key); // ② 树形查找 O(log n) while ((e = e.next) != null) { // ③ 链表遍历 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } } } return null; // ④ 未命中 } ``` #### hash 算法（JDK8） ```java static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } ``` **为什么这么做**：把 hashCode 的高 16 位异或到低 16 位，让高位也参与桶下标的计算。因为 `(n-1) & hash` 只用低位（n 是 2 的幂时 n-1 是低位全 1），如果没有扰动，高位信息就浪费了，容易碰撞。 **桶定位公式**：`index = (n - 1) & hash` - 容量 n 是 2 的幂时，`n-1` 的二进制是低 n 位全 1（如 16 = 10000, 15 = 01111） - `& 01111` 等价于"取低 4 位"，也等价于 `hash % 16` - 但按位与比取模运算快得多 **hashCode 和 equals 契约**： - equals 相等 → hashCode 必相等（正契约） - hashCode 相等 → equals 不一定相等（哈希冲突，反契约） - **打破后果**：put 时 A/B 的 hash 不同，equals 无法触发覆盖 → 两个 equals 相等的 key 各占一个桶；get 时可能找不到刚 put 的值 #### resize 扩容（JDK8） ```java final Node[] resize() { Node[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; // ① 首次扩容 if (oldCap == 0) { newCap = (oldThr > 0) ? oldThr : DEFAULT_INITIAL_CAPACITY; // 16 newThr = (int)(newCap * DEFAULT_LOAD_FACTOR); // 12 } // ② 达 MAX_CAP 不再扩容量，只增 threshold else if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // ③ 常规扩容：容量翻倍 else if ((newCap = oldCap << 1) > MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else { newThr = oldThr << 1; } @SuppressWarnings({"rawtypes","unchecked"}) Node[] newTab = (Node[])new Node[newCap]; table = newTab; // ④ 遍历旧表迁移元素 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node e = oldTab[j]; if (e == null) continue; oldTab[j] = null; if (e.next == null) { newTab[e.hash & (newCap - 1)] = e; // 单节点，直接算 } else if (e instanceof TreeNode) { ((TreeNode)e).split(this, newTab, j, oldCap); // 树桶：拆分，size<6 退化 } else { // 关键：链表按 e.hash & oldCap 拆成"原位"和"远端"两串 Node loHead = null, loTail = null; // e.hash & oldCap == 0 的 Node hiHead = null, hiTail = null; // e.hash & oldCap != 0 的 do { if ((e.hash & oldCap) == 0) { loTail = (loTail == null) ? loHead = e : loTail.next = e; } else { hiTail = (hiTail == null) ? hiHead = e : hiTail.next = e; } } while ((e = e.next) != null); if (loHead != null) newTab[j] = loHead; // 原位 if (hiHead != null) newTab[j + oldCap] = hiHead; // 远端 index+oldCap } } } threshold = newThr; return table; } ``` **为什么只判断 `e.hash & oldCap` 一个 bit**： - 容量从 oldCap 变成 newCap=oldCap×2，newCap-1 比 oldCap-1 多了一位 1（高位） - 原 index = hash & (oldCap-1)，只用了低 n 位 - 新 index = hash & (newCap-1)，多了第 n 位 - 所以新旧 index 差在第 n 位： - `e.hash & oldCap == 0`（第 n 位为 0）→ 新 index = 旧 index（原位） - `e.hash & oldCap != 0`（第 n 位为 1）→ 新 index = 旧 index + oldCap（远端） - **性能收益**：不用重新 hash，只判断一个 bit #### JDK7 vs JDK8 演进对比 | 维度 | JDK7 | JDK8 | 改动原因 | |------|------|------|---------| | 数据结构 | 数组 + 链表 | 数组 + 链表 + 红黑树 | 长链表 O(n) → O(log n) | | 头/尾插法 | 头插（`e.next = table[i]; table[i] = e`） | 尾插 | 头插法并发扩容形成环形链表 | | 树桶 | 无 | TreeNode（继承 LinkedHashMap.Entry） | 双向链表 + 树指针 | | hash 算法 | `hash(indexFor(hash, n))` 简单取模 | `h ^ (h >>> 16)` 高位异或 | 高位参与运算减少碰撞 | | resize 新 index | 重新 `indexFor(e.hash, newCap)` | `e.hash & oldCap == 0 ? i : i + oldCap` | 位运算比重新 hash 快 | | 转树 | 无 | 链长>8 且容量≥64 | 泊松分布下的合理阈值 | | 树退化 | 无 | 扩容后树桶 size<6 | 扩容分散后冲突降低 | | 并发安全 | 头插法有环形链表风险 | 尾插法安全（但整体仍非线程安全） | 修特定 bug | | 函数式 API | 无 | compute/computeIfAbsent/computeIfPresent/merge | 配合 lambda | #### 转树与退化的双门槛 **为什么链长阈值 8**：HashMap 容量是 2 的幂，负载因子 0.75，链长分布近似泊松分布。泊松分布下链长到 8 的概率约 `6 × 10⁻⁸`——极端小，说明链长到 8 大概率是哈希冲突而非随机分布，此时红黑树 O(log n) 优势才体现。 **为什么容量阈值 64**：桶数太少时冲突是正常现象，转树成本大于扩容；容量到 64 之前应该优先扩容解决冲突，而不是转树。 #### 并发问题六大分类 | # | 问题 | 表现 | 根因 | |---|------|------|------| | 1 | **size 计数错乱** | `size()` 返回小于实际 | `++size` 非原子（read-modify-write） | | 2 | **put 覆盖丢失** | 两个线程 put 同一 key，只留一个 | 无锁检查-写入不原子 | | 3 | **get 返回 null** | 命中正在迁移的桶读到空 | resize 期间新旧桶切换非原子 | | 4 | **迭代 CME** | `ConcurrentModificationException` | fail-fast modCount 检测 | | 5 | **check-then-act 竞态** | `if (!containsKey(k)) put(k, v)` 之间被插入 | 复合操作无原子保证 | | 6 | **内存可见性缺失** | 其他线程看不到最新值 | 普通变量无 volatile | **JDK8 尾插法"修好了"什么**：只修了头插法在并发扩容时形成环形链表的这个特定 bug。其他 5 类问题仍然存在。**HashMap 仍然非线程安全**。 #### 替代方案对比 | 方案 | 锁粒度 | 读写并发 | 迭代 | 适用 | |------|-------|---------|------|------| | `ConcurrentHashMap` | 桶级 `synchronized` + CAS | 读几乎无锁 | 弱一致 | **默认首选** | | `Collections.synchronizedMap` | 全表 `synchronized` | 串行 | 迭代需外层加锁 | 低并发简单场景 | | `ConcurrentSkipListMap` | 桶级（跳表） | 读几乎无锁 | 弱一致 | 需要有序 | | `Collections.unmodifiableMap` | 无 | 只读 | 迭代安全 | 只读场景 | | 自加锁 | 用户自定义 | 用户控制 | 用户控制 | 复合操作 | **工程实践**： - 默认用 `ConcurrentHashMap` - 复合操作（如"不存在则创建"）用 `computeIfAbsent` 保证原子 - 不可变场景用 `unmodifiableMap` - 共享计数器用 `LongAdder`/`AtomicLong`，不要用 Map 存计数 ### STEP 4 · 简化 > **一句话总结**：HashMap 是"数组+链表+红黑树"三层结构，JDK8 用 `hash 高位异或` + `尾插法` + `resize 位运算` + `链长>8 转树` 四大优化解决查找、扩容、并发三个痛点，但并发正确性仍需 `ConcurrentHashMap`。 ## 常见误区 - **误区 1**：HashMap 头插法改成尾插法就线程安全了 → 错，只修了环形链表 bug，其他 5 类并发问题仍在 - **误区 2**：`(n-1) & hash` 什么时候等价于 `hash % n` → 只有容量 n 是 2 的幂时才等价 - **误区 3**：链长到 8 就必然转树 → 错，还要求桶数 ≥ 64，否则优先扩容 - **误区 4**：HashMap 完全不支持 null → 错，允许 1 个 null key（放 0 号桶）和多个 null value；`Hashtable`/`ConcurrentHashMap` 才不允许 - **误区 5**：转树后就是永久的红黑树 → 错，扩容后树桶 size < 6 会退化回链表 - **误区 6**：`hashCode` 相等则 `equals` 相等 → 错，正契约是 `equals` 相等则 `hashCode` 必相等；`hashCode` 相等只代表哈希冲突 ## 延伸追问 1. **为什么 HashMap 容量必须为 2 的幂？** - `(n-1) & hash` 等价于 `% n` 只在 n 是 2 的幂时成立；扩容时 `e.hash & oldCap` 判断一个 bit 就能决定新位置；低 16 位散列均匀 2. **`hashCode` 和 `equals` 契约是什么？破坏会怎样？** - 契约："equals 相等则 hashCode 必相等"（反过来不成立）；破坏后果：put 时 A/B hash 不同 → equals 无法触发覆盖 → 两个 equals 相等的 key 各占一个桶；get 时可能找不到刚 put 的值 3. **`e.hash & oldCap` 位运算优化的数学原理？** - 容量翻倍后 newCap-1 相当于 oldCap-1 前面多了一位 1（第 n 位）；e.hash 的第 n 位为 0 → 新 index = 旧 index；为 1 → 新 index = 旧 index + oldCap 4. **JDK7 头插法为什么会 CPU 100%？** - 并发扩容时两线程同时迁移链表，A 遍历 e→f，B 遍历 f→e，A 完成后 e→f→e 环；get 命中该桶死循环 5. **HashMap 为什么默认容量 16、负载因子 0.75？** - 16 是内存开销和扩容频率的折中；0.75 是泊松分布下平均链长期望约 0.5 的经验值 6. **`computeIfAbsent` 在 HashMap 和 ConcurrentHashMap 上有什么差异？** - HashMap 上无原子性保证，需要外层同步；ConcurrentHashMap 上桶级 synchronized 保证 check-then-act 原子 7. **HashMap 大量扩容时怎么优化？** - 预估容量 `new HashMap<>(expectedSize / 0.75f + 1)`；使用 `computeIfAbsent` 减少重哈希；批量导入用 `Collectors.toMap` 后合并 ## 速查表（面试前 60 秒扫完） ``` 数据结构：数组 + 链表 + 红黑树（JDK8+） put 四步： ① hash(key) = key.hashCode() ^ (key.hashCode() >>> 16) ② index = (n - 1) & hash ③ 桶空 → 直放；桶非空 → 遍历 equals 覆盖或尾插 ④ 链长>8 且容量≥64 转树；size>threshold 扩容 resize 五步（JDK8）： ① 首次：newCap=16，threshold=12 ② 常规：newCap=oldCap<<1，threshold=oldThr<<1 ③ 达 MAX_CAP(1<<30)：只增 threshold ④ 遍历旧桶，按 e.hash & oldCap 拆两串 ⑤ 树桶 split，size<6 退化回链表 JDK7→JDK8 七改动： 头插→尾插 / 引入红黑树 / hash 位运算 / resize 位运算 / TreeNode 拆分 / 转树双门槛 / 新增函数式 API 并发问题六类： size 错乱 / put 覆盖 / get null / 迭代 CME / check-then-act / 可见性缺失 替代方案：ConcurrentHashMap 首选 关键常量： TREEIFY_THRESHOLD=8, UNTREEIFY_THRESHOLD=6, MIN_TREEIFY_CAPACITY=64 DEFAULT_INITIAL_CAPACITY=16, DEFAULT_LOAD_FACTOR=0.75 ``` ## 关联题目（题库） - [ ] 《HashMap在get和put时经过哪些步骤？》— 2026-10-09 Round 1 Q4, ⭐⭐⭐（漏 hash 位运算、get 树形分支） - [ ] 《HashMap是如何扩容的？》— 2026-10-09 Round 1 Q5, ⭐⭐（只答触发条件，无扩容过程） - [ ] 《JDK1.8中HashMap有哪些改变？》— 2026-10-09 Round 1 Q6, ⭐⭐⭐（漏 hash 算法、Node 拆分、树退化） - [ ] 《HashMap用在并发场景中有什么问题？》— 2026-10-09 Round 1 Q7, ⭐⭐⭐（漏 get 中间态、CME、check-then-act） - [ ] 《HashMap、Hashtable和ConcurrentHashMap的区别？》— 2026-10-09 Round 1 Q2, ⭐⭐⭐（主线对，广度不足） ## 关联知识 - [ConcurrentHashMap 并发机制与 synchronized 决策](./hash-map-concurrent.md) - [红黑树原理与 5 条性质](./red-black-tree.md) - [String 的三大设计模式](./string-design-patterns.md) ## Anki 候选卡片 1. **正**：HashMap JDK8 的 hash 算法？ **反**：`hash(key) = (h = key.hashCode()) ^ (h >>> 16)`——高 16 位异或到低 16 位参与运算 2. **正**：HashMap 桶定位公式？为什么等价于取模？ **反**：`index = (n - 1) & hash`；当容量 n 是 2 的幂时 n-1 低位全 1，`& (n-1)` 等价于 `% n` 3. **正**：JDK8 HashMap resize 位运算优化的关键公式？ **反**：`e.hash & oldCap == 0 ? 原位 : 新index = oldIndex + oldCap`——容量翻倍后新旧 index 只差第 n 位，一个 bit 判断新位置 4. **正**：HashMap 转树的双门槛？ **反**：链长 > 8 且容量 ≥ 64；扩容后树桶 size < 6 退化回链表 5. **正**：JDK7 头插法为什么会 CPU 100%？ **反**：并发扩容时两线程同时迁移，A 遍历 e→f、B 遍历 f→e，A 完成后 e→f→e 环，get 命中死循环 6. **正**：JDK7 vs JDK8 HashMap 七大改动？ **反**：① 引入红黑树；② 头插→尾插；③ hash 算法 `h^(h>>>16)`；④ resize 位运算；⑤ TreeNode 拆分；⑥ 转树双门槛 8+64；⑦ 新增函数式 API 7. **正**：HashMap 并发问题六类？ **反**：① size 计数错乱；② put 覆盖丢失；③ get 中间状态返回 null；④ 迭代 CME；⑤ check-then-act 竞态；⑥ 内存可见性缺失 8. **正**：hashCode 和 equals 契约？破坏后果？ **反**：equals 相等则 hashCode 必相等；破坏后果：put 时 equals 无法触发覆盖、get 时找不到刚 put 的值 --- *最后更新：2026-10-09*