JDK8 HashMap 底层原理全解析

从设计动机到源码细节（面试友好版）

HashMap 是 Java 中使用最频繁的数据结构之一，同时也是面试必考。
本文基于 JDK8+，从整体结构到核心源码，系统讲清 HashMap 的底层原理。

---

一、HashMap 整体结构概览

1.1 数据结构

HashMap 底层采用：

数组（桶 table） + 链表 + 红黑树

table (Node<K,V>[])
 ├── bucket[0] -> Node -> Node -> ...
 ├── bucket[1] -> TreeNode (红黑树)
 ├── bucket[2] -> null
 └── ...

• 数组负责 定位
• 链表解决 哈希冲突
• 红黑树优化 极端冲突场景

---

⭐ 面试高频总结

HashMap 在 JDK8 之后采用「数组 + 链表 / 红黑树」结构，
当单个桶中元素过多时，用红黑树将最坏时间复杂度从 O(n) 降为 O(log n)。

---

二、HashMap 的创建过程（懒初始化）

2.1 构造函数并不会立即分配桶数组

new HashMap<>();

• 不会立刻创建 table
• table 在 第一次 put 时 才初始化

2.2 默认参数

DEFAULT_INITIAL_CAPACITY = 16
DEFAULT_LOAD_FACTOR = 0.75

• 默认桶数：16
• 默认负载因子：0.75
• 默认扩容阈值：16 × 0.75 = 12

---

⭐ 面试高频总结

HashMap 采用懒初始化，桶数组在第一次 put 时才创建，
默认容量是 16，默认负载因子是 0.75。

---

三、HashMap 的 hash 计算原理

3.1 是否直接使用 key.hashCode()？

不是直接使用，而是做了扰动处理。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

3.2 为什么要扰动？

• 桶下标只使用 hash 的 低位
• 扰动让 高位信息参与进低位
• 减少哈希冲突

---

⭐ 面试高频总结

HashMap 使用 hashCode() 并通过 h ^ (h >>> 16) 进行扰动，
以提升低位分布的均匀性，降低冲突概率。

---

四、桶下标的计算方式

index = (n - 1) & hash;

为什么不用 % n？

• 位运算更快
• 要求 n 必须是 2 的幂
• 为扩容提供数学基础

---

⭐ 面试高频总结

HashMap 要求容量是 2 的幂，是为了使用 (n-1)&hash 快速定位桶，
并支持高效的扩容重分布。

---

五、put 插入流程（核心）

5.1 插入流程概览

put(key,value)
 ├── 初始化 table（如有必要）
 ├── 计算 hash
 ├── 定位桶 index
 ├── 处理冲突（覆盖 / 链表 / 红黑树）
 ├── size++
 └── 判断是否扩容

---

5.2 链表与红黑树的转换条件

TREEIFY_THRESHOLD = 8
MIN_TREEIFY_CAPACITY = 64

• 链表长度 ≥ 8
• 且 table.length ≥ 64
• 否则优先扩容而不是树化

---

⭐ 面试高频总结

链表长度达到 8 并且 HashMap 容量至少为 64 时才会树化，
目的是避免在小容量下过早引入红黑树的维护成本。

---

六、扩容机制（resize）——JDK8 精华

6.1 扩容触发条件

if (size > threshold) {
    resize();
}

• threshold = capacity × loadFactor

---

6.2 扩容后的关键结论

元素的新位置只可能是：

• 原 index
• 原 index + oldCap

6.3 判断依据

if ((hash & oldCap) == 0) {
    // 位置不变
} else {
    // index + oldCap
}

• 不重新计算 hash
• 只检查扩容新增的那一位二进制

---

⭐ 面试高频总结

JDK8 扩容不再重新计算 hash，而是通过 hash & oldCap 判断元素位置，
这是 HashMap 扩容性能提升的关键。

---

七、get 查找流程

get(key)
 ├── 计算 hash
 ├── 定位桶
 ├── 桶为空 → 返回 null
 ├── 桶为树 → 红黑树查找
 └── 桶为链表 → 顺序遍历

• 平均时间复杂度：O(1)
• 最坏情况（红黑树）：O(log n)

---

⭐ 面试高频总结

HashMap 的 get 平均复杂度是 O(1)，
在极端冲突情况下通过红黑树保证 O(log n)。

---

八、remove 删除机制

8.1 removeNode 的核心参数

removeNode(hash, key, value, matchValue, movable)

• matchValue = false：只比较 key
• matchValue = true：key 和 value 都必须匹配

8.2 结构性修改

• size--
• modCount++

---

⭐ 面试高频总结

HashMap 删除操作会增加 modCount，用于 fail-fast 机制。

---

九、fail-fast 机制（modCount）

• 迭代器创建时保存 expectedModCount
• 遍历过程中检测结构性修改
• 不一致直接抛 ConcurrentModificationException

---

⭐ 面试高频总结

modCount 用于 fail-fast，不保证线程安全，只用于快速发现错误用法。

---

十、为什么容量必须是 2 的幂？（tableSizeFor）

10.1

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 :
           (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY :
           n + 1;
}

10.2 原理说明

• cap-1 处理“已是 2 的幂”的情况
• 位扩散把最高位以下全部置 1
• +1 得到最近的 2 的幂

---

⭐ 面试高频总结

HashMap 通过位扩散 +1 的方式在 O(1) 时间内将容量调整为最近的 2 的幂。

---

十一、HashMap 面试终极总结（30 秒版）

HashMap 底层是数组 + 链表/红黑树；
通过扰动后的 hash 用 (n−1)&hash 定位桶；
链表长度 ≥8 且容量 ≥64 时树化；
size 超过 capacity×0.75 触发扩容；
扩容时桶翻倍，元素通过 hash&oldCap 重新分布；
非线程安全，通过 modCount 实现 fail-fast。