03.2 — HashMap 核心原理
定位: Java 中使用频率最高的数据结构 — 哈希表的设计哲学、冲突解决、扩容优化 面试高频度: ⭐⭐⭐⭐⭐ 考查方式: put/get 全流程、哈希冲突解决、扩容机制、红黑树优化、线程安全问题
一、这是什么？为什么需要它？
是什么
HashMap 是基于哈希表的 Map 接口实现——以 key-value 形式存储数据，通过 key 的 hashCode 直接定位存储位置，实现平均 O(1) 的查找性能。
为什么需要 HashMap？
没有哈希表会怎样？
用 List 存储键值对：[("name", "Alice"), ("age", 25), ...]
查找 "name" 的值 → 遍历整个 List → O(n)
100万条数据 → 最坏要查100万次
有了哈希表：
"name".hashCode() → 直接定位到存储位置 → O(1)
100万条数据 → 通常 1-2 次比较即可找到
核心：空间换时间 — 用额外桶数组换取 O(1) 查找二、原理拆解
2.1 核心数据结构（JDK 8）
┌─────────────────────────────────────────────────────────────┐
│ HashMap 内部结构 │
│ │
│ Node<K,V>[] table (桶数组) │
│ ┌────┬────┬────┬────┬────┬────┬────┬────┐ │
│ │ │ │ │ │ │ │ │ │ ← 数组 (bucket) │
│ ├────┼────┼────┼────┼────┼────┼────┼────┤ │
│ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ │
│ └─┬──┴─┬──┴─┬──┴─┬──┴─┬──┴─┬──┴─┬──┴─┬──┘ │
│ │ │ │ │ │ │ │ │ │
│ null │ null │ null │ null │ null │
│ │ │ │
│ ▼ ▼ │
│ ┌──────────┐ ┌──────────┐ │
│ │ Node A │ │ Node D │ 链表 (当冲突少) │
│ │ key:a │ │ key:d │ │
│ │ next ────┼──→ │ next ────┼──→ null │
│ └──────────┘ └──────────┘ │
│ │
│ > 8个 → 红黑树 (当冲突多) │
│ │
│ 初始容量 = 16 (必须是2的幂) │
│ 负载因子 = 0.75 │
│ 阈值 = capacity * loadFactor = 12 │
└─────────────────────────────────────────────────────────────┘2.2 hash() 扰动函数
java
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}为什么要异或高16位？
key.hashCode() = 0x12345678
h >>> 16 = 0x00001234
h ^ (h>>>16) = 0x1234464C (高16位和低16位混合)
计算桶位置：(n - 1) & hash
如果 n=16（默认容量）：
(16-1) & hash = 15 & hash = 低4位
如果不做扰动，h >>> 16 就是 0
→ 只有低 4 位参与桶定位 → 很多 hash 冲突
→ 扰动后，高16位也参与 → 减少冲突
所以：扰动函数是为了让 hashCode 的高位也能参与桶定位2.3 put 流程全链路
java
public V put(K key, V value) {
// 1. 哈希
int hash = hash(key);
// 2. 计算桶索引 (n-1) & hash（n 是 table 长度）
int i = (table.length - 1) & hash;
// 3. 桶为 null → 直接放入
if (table[i] == null) {
table[i] = newNode(hash, key, value, null);
} else {
// 4. 桶不为 null → 遍历
Node<K,V> e = table[i];
if (e.hash == hash && (e.key == key || key.equals(e.key))) {
e = e; // key 已存在，准备替换
} else {
// 遍历链表或红黑树
if (e instanceof TreeNode) {
e = ((TreeNode)e).putTreeVal(this, tab, hash, key, value);
} else {
for (int binCount = 0; ; binCount++) {
if (e.next == null) {
e.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // 7 → 树化
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ...equals...) {
break; // 找到旧 key
}
e = e.next;
}
}
}
// 5. 替换旧值
if (e != null) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
// 6. 扩容检查
if (++size > threshold) resize();
}2.4 扩容机制
触发条件：size > threshold (= capacity * 0.75)
扩容过程：
1. 新容量 = 旧容量 << 1 (2倍)
2. 新阈值 = 新容量 * 0.75
3. 创建新数组 (新容量)
4. 元素重新散列
为什么扩容是 2 倍？
因为桶定位是 (n-1) & hash
n 是 2 的幂 → n-1 的二进制全为 1
→ 定位 = 取 hash 的低 log2(n) 位，分布均匀
重新散列的优化（JDK8）：
元素在新数组的位置 = 原位置 或 原位置 + 旧容量
因为 hash & oldCap == 0 → 在原位置
== 1 → 在原位置 + oldCap
例：容量从 16 → 32
hash = 0bXXXX (低5位决定位置)
旧位置 = hash & 0b1111 (低4位)
hash 的第5位是 0 → 位置不变
hash 的第5位是 1 → 位置 = 旧位置 + 162.5 红黑树优化
为什么链表 > 8 时要转红黑树？
链表查找：遍历链表 O(n)
红黑树查找：平衡二叉树 O(log n)
当哈希冲突严重时：
链表长度 10000 → 查找 10000 次 ❌
红黑树 10000 → 查找 ~14 次 ✅
为什么阈值是 8？
泊松分布概率：0.75负载因子下，
链表长度 8 的概率 < 千万分之一
→ 触发树化说明 hashCode 严重分布不均
→ 但一旦触发，红黑树 O(log n) 兜底
树化条件：
链表长度 > 8 AND table.length >= 64
如果 table.length < 64 → 先扩容三、图解全景
┌─────────────────────────────────────────────────────────────┐
│ HashMap put 流程全图 │
│ │
│ put(key, value) │
│ │ │
│ ▼ │
│ hash = key.hashCode() ^ (key.hashCode() >>> 16) │
│ │ │
│ ▼ │
│ i = (table.length - 1) & hash ← 桶索引 │
│ │ │
│ ▼ │
│ table[i] == null? │
│ ┌──┴──┐ │
│ YES NO │
│ │ │ │
│ ▼ ▼ │
│ 直接放入 遍历链表/红黑树 │
│ │ │
│ ├── key 已存在 → 替换 value │
│ └── key 不存在 → 插入尾部 │
│ │ │
│ ▼ │
│ 链表长度 > 8? │
│ ┌──┴──┐ │
│ YES NO │
│ │ │ │
│ ▼ ▼ │
│ table≥64? 继续链表 │
│ ┌──┴──┐ │
│ YES NO → 扩容 │
│ │ │
│ ▼ │
│ 转红黑树 │
│ │
│ size > threshold? → resize() → 扩容 2 倍 │
└─────────────────────────────────────────────────────────────┘四、实战验证
4.1 哈希冲突验证
java
// 用 String 演示哈希冲突
String s1 = "Aa";
String s2 = "BB";
System.out.println(s1.hashCode()); // 2112
System.out.println(s2.hashCode()); // 2112 ← 冲突！
Map<String, String> map = new HashMap<>();
map.put("Aa", "value1"); // 放入桶 2112 & 15
map.put("BB", "value2"); // 冲突，链表第二个节点4.2 扩容观察
java
// 通过反射观察 HashMap 容量
HashMap<String, String> map = new HashMap<>();
// 初始 table = null (懒加载)
for (int i = 0; i < 13; i++) { // 16 * 0.75 = 12，第13个触发扩容
map.put("key" + i, "value" + i);
}
// 扩容后容量 = 32五、面试视角
| 追问 | 答案要点 |
|---|---|
| HashMap 为什么是 O(1) 查找？ | 哈希函数直接定位桶，均摊 O(1)，最坏 O(log n)（红黑树） |
| 负载因子为什么是 0.75？ | 泊松分布优化，平衡冲突率和空间利用率 |
| 为什么容量是 2 的幂？ | (n-1) & hash 等价于取模，且分布均匀 |
| JDK 7 和 JDK 8 的 HashMap 区别？ | 头插→尾插（避免死循环）；数组+链表→+红黑树；扩容优化 |
| HashMap 线程安全吗？不安全会怎么样？ | 不安全。JDK7 扩容可能死循环，JDK8 可能数据丢失 |
| key 为 null 是怎么处理的？ | hash = 0，放到 table[0] 桶中 |
📚 相关链接
- **ConcurrentHashMap** — 线程安全的 HashMap
- **Set与Queue** — HashSet 基于 HashMap
- **Object类与通用方法** — hashCode() 的重要性
- ← 返回 **集合索引**