本文主要结合 JDK8 之后的 HashMap 源码思想，系统讲清楚 Java 中 HashMap 的底层原理（数组 + 铉表 + 红黑树）。
# 一、HashMap 总体结构
JDK8 中 HashMap 的核心结构：
数组（Node<K,V>[] table）
↓
数组每个位置是一个链表
↓
链表过长转为红黑树
即：
数组 + 链表 + 红黑树
核心成员变量（JDK8）：
transient Node<K,V>[] table; // 哈希桶数组 | |
transient int size; // 元素个数 | |
int threshold; // 扩容阈值 | |
final float loadFactor; // 负载因子 |
# 二、底层数据结构
# 1️⃣ Node 结构（源码精简）
static class Node<K,V> implements Map.Entry<K,V> { | |
final int hash; | |
final K key; | |
V value; | |
Node<K,V> next; | |
} |
本质就是一个 单向链表节点
# 2️⃣ 数组结构示意
table[0]
table[1] → Node → Node → Node
table[2]
table[3] → Node → Node (红黑树)
# 三、HashMap 的核心流程
我们按源码逻辑讲 4 个核心问题：
- hash 如何计算？
- put 如何插入？
- 为什么容量必须是 2 的幂？
- 扩容如何实现？
# 四、hash 计算原理
源码（JDK8）：
static final int hash(Object key) { | |
int h; | |
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); | |
} |
# 为什么要右移 16 位异或？
因为：
数组下标计算 = (n - 1) & hash
如果只用低位，会导致高位信息浪费。
异或操作让：
高 16 位影响低 16 位
降低 hash 冲突。
# 五、数组下标如何确定？
int index = (n - 1) & hash; |
假设：
n = 16
n-1 = 15 = 00001111
那么：
hash & 00001111
只取低 4 位。
# ⭐ 为什么容量必须是 2 的幂？
因为：
n-1 才会变成 111111 二进制
例如：
16 = 10000
15 = 01111
这样：
& 运算 = 等价于 % 16
效率远高于取模运算。
# 六、put () 插入流程（源码逻辑分析）
源码核心方法：
public V put(K key, V value) { | |
return putVal(hash(key), key, value, false, true); | |
} |
核心逻辑（简化版）：
if (table 为空) | |
resize(); | |
计算桶位置 | |
如果该位置为空 | |
直接 new Node | |
否则 | |
如果 key 相同 | |
覆盖值 | |
否则 | |
遍历链表 | |
找到相同key就覆盖 | |
没找到就尾插 | |
如果链表长度 >= 8 | |
转红黑树 |
# 七、链表什么时候转红黑树？
源码条件：
if (binCount >= TREEIFY_THRESHOLD - 1) // 8 | |
treeifyBin(...) |
# 触发条件：
| 条件 | 值 |
|---|---|
| 链表长度 ≥ 8 | 才会考虑树化 |
| 数组长度 ≥ 64 | 才真的树化 |
如果数组长度 < 64：
会优先扩容，而不是树化。
# 为什么？
因为：
冲突可能是容量太小，不是 hash 分布问题。
# 八、红黑树的作用
时间复杂度变化：
| 结构 | 查找复杂度 |
|---|---|
| 链表 | O(n) |
| 红黑树 | O(log n) |
JDK8 优化目的：
防止恶意 hash 冲突攻击导致性能退化
# 九、resize 扩容机制（重点）
触发条件：
size > threshold
而：
threshold = capacity * loadFactor
默认 loadFactor = 0.75
# 扩容步骤
容量翻倍：
newCap = oldCap << 1
然后重新分布元素。
# ⭐ JDK8 的高效 rehash 算法（重点）
JDK7 做法：
重新计算 hash，重新取模
JDK8 优化：
只看 hash 的 新增那一位：
if ((e.hash & oldCap) == 0) | |
放在原位置 | |
else | |
放到 原位置 + oldCap |
举例：
原容量 16 → 扩容到 32
只判断：
hash & 16
是 0 还是 1。
# 为什么可行？
因为容量翻倍 = 高位多一位
原索引：
(n-1) & hash
扩容后：
(2n-1) & hash
等于：
原索引 或 原索引 + oldCap
因此：
不需要重新算 hash，性能大幅提升
# 十、get () 查找流程
public V get(Object key) |
步骤：
- 计算 hash
- 找到桶位置
- 如果是红黑树 → 树查找
- 如果是链表 → 顺序查找
- key.equals 比较
# 十一、HashMap 为什么线程不安全？
因为没有任何同步。
典型问题：
# 1️⃣ 多线程 resize 死循环（JDK7）
链表可能形成环。
JDK8 虽然优化了头插法问题，但依然不安全。
# 十二、HashMap 的时间复杂度
| 操作 | 平均 | 最坏 |
|---|---|---|
| put | O(1) | O(log n) |
| get | O(1) | O(log n) |
# 十三、JDK7 vs JDK8 区别
| 特性 | JDK7 | JDK8 |
|---|---|---|
| 数据结构 | 数组 + 链表 | 数组 + 链表 + 红黑树 |
| 插入方式 | 头插法 | 尾插法 |
| 扩容机制 | 全量 rehash | 高位判断优化 |
| 并发风险 | 可能死循环 | 不会死循环 |
# 十四、完整执行流程总结
插入数据：
key → hash()
→ (n-1)&hash 定位数组
→ 桶为空 → new Node
→ 桶不为空 → 链表/树插入
→ size++
→ 判断是否扩容
# 十五、设计思想总结
HashMap 本质就是解决三件事：
- 如何减少 hash 冲突（扰动函数）
- 如何降低冲突代价（红黑树）
- 如何让扩容更高效（高位判断）
# 十六、一句话总结
HashMap = 通过 hash 定位数组桶，冲突用链表解决，链表长了转红黑树，容量翻倍用高位运算优化迁移。
如果你愿意，我可以再带你：
- 从源码逐行演示一次 put 流程
- 或手写一个简化版 HashMap
- 或讲面试中 HashMap 高级考点
你想深入哪块？
