面试必备：HashMap 原理深度解析
前言
HashMap 是 Java 面试中的高频考点，几乎每个面试官都会问到。这篇文章用图解 + 核心代码，带你彻底搞懂 HashMap。
数据结构演进
JDK 1.7 之前：数组 + 链表
[table数组]
│
├── 桶0 → [Node] → [Node] → null (链表解决哈希冲突)
├── 桶1 → null
├── 桶2 → [Node] (单个节点)
└── ...
问题：链表过长时，查询时间复杂度退化为 O(n)
JDK 1.8 开始：数组 + 链表 + 红黑树
[table数组]
│
├── 桶0 → [Node] → [Node] → [Node] (链表长度<8，仍用链表)
├── 桶1 → [TreeNode] → [TreeNode] (链表长度≥8，转红黑树)
└── ...
优化：当链表长度超过 8 时，自动转为红黑树，查询时间复杂度从 O(n) → O(log n)
核心原理
1. 哈希计算
// HashMap 的 hash 方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 计算数组下标
int index = (n - 1) & hash
为什么用 h ^ (h >>> 16)？
- 把 hashCode 的高 16 位和低 16 位进行异或
- 让高位也参与运算，减少哈希冲突
2. put 流程图
put(key, value)
│
▼
① 计算 hash 值
│
▼
② 计算数组下标 (n-1) & hash
│
▼
③ 桶为空？──是──→ 直接插入
│
否
│
▼
④ 桶中已有节点
│
├── key 相同？──是──→ 覆盖 value
│
否
│
├── 是红黑树节点？──是──→ 红黑树插入
│
否
│
└── 链表插入
│
├── 链表长度 ≥ 8？──是──→ 转为红黑树
│
└── 插入尾部
3. 扩容机制
// 扩容条件：元素数量 > 阈值
// 阈值 = 容量 × 负载因子（默认 0.75）
// 扩容时容量翻倍
newCap = oldCap << 1 // 16 → 32 → 64 → ...
// 所有元素重新哈希（这是个性能损耗点！）
扩容时机：元素数量达到 容量 × 0.75 时触发
扩容过程：新建数组，重新计算每个元素的位置（全部 rehash）
4. 初始容量选择
// 如果预估有 1000 个元素，推荐这样创建
// 1000 / 0.75 + 1 = 1334，再找最近的 2 的幂：2048
Map<Integer, String> map = new HashMap<>(2048);
为什么建议指定初始容量？
- 避免频繁扩容
- 每次扩容都需要 rehash，影响性能
线程安全问题
HashMap 不是线程安全的！
并发场景下的问题
- 数据覆盖：两个线程同时 put，可能覆盖对方的数据
- 死循环：JDK 1.7 扩容时，头插法可能导致环形链表，get 时死循环
- ConcurrentModificationException：迭代时修改结构
解决方案
| 方案 | 特点 |
|---|---|
Hashtable | synchronized，效率低，已淘汰 |
Collections.synchronizedMap() | 包装后加锁，同步方法 |
ConcurrentHashMap | 推荐，分段锁 / CAS，效率高 |
// 推荐写法
Map<String, Object> map = new ConcurrentHashMap<>();
JDK 1.7 vs 1.8 区别
| 特性 | JDK 1.7 | JDK 1.8 |
|---|---|---|
| 数据结构 | 数组 + 链表 | 数组 + 链表 + 红黑树 |
| 插入方式 | 头插法 | 尾插法 |
| 扩容 | 重新哈希 | 重新哈希 |
| 哈希算法 | 9次扰动 | 2次扰动 |
面试高频问题
Q1：为什么链表转红黑树的阈值是 8？
统计学结论：哈希值均匀分布时，单个桶中节点数超过 8 的概率不到千万分之一。
// 源码注释
/**
* Because TreeNodes are about twice the size of regular nodes,
* we only use them when bins contain enough nodes to warrant
* use (TREEIFY_THRESHOLD = 8).
*/
Q2：负载因子为什么是 0.75？
时间和空间的权衡：
- 太小（如 0.5）：扩容频繁，空间浪费
- 太大（如 1.0）：哈希冲突增多，查询变慢
- 0.75 是经验和统计得出的平衡点
Q3：HashMap 的容量为什么是 2 的幂？
index = (n - 1) & hash
n - 1是11111...形式的二进制- 与 hash 进行
&运算，相当于取模，但效率更高
Q4：为什么重写 equals 必须重写 hashCode？
// 两个对象 equals 相等，hashCode 必须相等
Student s1 = new Student("张三", 18);
Student s2 = new Student("张三", 18);
s1.equals(s2) // true
s1.hashCode() == s2.hashCode() // 必须 true，否则 HashMap 查询会出问题
总结
- 数据结构：数组 + 链表（JDK 1.8 加了红黑树）
- 核心：哈希计算、扩容机制、并发问题
- 高频考点：put 流程、扩容时机、线程安全、1.7 vs 1.8 区别