HashMap 底层实现：从数组到红黑树
HashMap 不是哈希表，是「数组 + 链表 + 红黑树」
很多人以为 HashMap 就是「哈希表」，但它的底层结构经历了两次进化：
- JDK 1.7：数组 + 链表（头插法）
- JDK 1.8+：数组 + 链表/红黑树（尾插法）——加入红黑树是为了解决链表过长导致的性能退化问题。
核心数据结构
java
public class HashMap<K, V> extends AbstractMap<K,V> {
// 哈希桶数组
transient Node<K, V>[] table;
// 键值对数量
transient int size;
// 扩容阈值 = 容量 × 负载因子
int threshold;
// 负载因子，默认 0.75
final float loadFactor;
}关键参数：
| 参数 | 默认值 | 说明 |
|---|---|---|
| DEFAULT_INITIAL_CAPACITY | 16 | 初始桶数量（必须是 2 的幂） |
| DEFAULT_LOAD_FACTOR | 0.75 | 负载因子 |
| TREEIFY_THRESHOLD | 8 | 链表转红黑树的阈值 |
| UNTREEIFY_THRESHOLD | 6 | 红黑树转回链表的阈值 |
| MIN_TREEIFY_CAPACITY | 64 | 最小树形化容量（数组太小不转树） |
Node 节点
java
static class Node<K, V> implements Map.Entry<K, V> {
final int hash; // key 的哈希值（避免重复计算）
final K key; // 不可变
V value; // 可以变
Node<K, V> next; // 链表下一节点
}哈希函数：如何把 key 变成数组索引
hash() 方法
java
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}为什么要 ^ (h >>> 16)？因为数组长度通常很小（如 16），直接用 hashCode() 的低 4 位会产生大量冲突。用高位和低位异或混合，能让哈希分布更均匀。
索引计算
java
int index = (n - 1) & hash; // n 是数组长度，必须是 2 的幂
// 等价于 hash % n，但位运算更快put() 流程详解
putVal 源码（简化）
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<K,V>[] tab; Node<K,V> p; int n, i;
// 第一步：数组为空或长度为 0，扩容初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 第二步：计算桶位置，桶为空，直接创建节点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 第三步：桶不为空，检查第一个节点
if (p.hash == hash &&
((k = p.key) == key || key.equals(k)))
e = p;
// 第四步：第一个节点不匹配，检查是否是红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 第五步：否则遍历链表
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 第六步：链表长度 ≥ 8，转红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || key.equals(k)))
break;
p = e;
}
}
// 第七步：key 已存在，替换旧值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 第八步：修改次数递增，检查扩容
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}流程图
put("hello", 1) 时：
┌─────────────────────────────────────────────────────────────┐
│ 第一步：数组为空？ │
│ └─ 是 → resize() 初始化数组（容量 16） │
└─────────────────────────────────────────────────────────────┘
↓
┌─────────────────────────────────────────────────────────────┐
│ 第二步：计算桶位置 │
│ hash("hello") = 31 │
│ index = 31 & 15 = 15 ← 在 bucket[15] 找 │
└─────────────────────────────────────────────────────────────┘
↓
┌─────────────────────────────────────────────────────────────┐
│ 第三步：bucket[15] 为空？ │
│ └─ 是 → 直接插入 Node │
│ └─ 否 → 遍历链表/红黑树，找相同 key 或遍历到末尾 │
└─────────────────────────────────────────────────────────────┘
↓
┌─────────────────────────────────────────────────────────────┐
│ 第四步：key 已存在？ │
│ └─ 是 → 替换旧值，返回旧值 │
│ └─ 否 → 插入新节点，检查是否需要转红黑树 / 扩容 │
└─────────────────────────────────────────────────────────────┘get() 流程：和 put 相反
java
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> 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<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}扩容机制：容量翻倍，元素重分配
扩容触发条件
当 size > threshold 时触发扩容
threshold = capacity × loadFactor = 16 × 0.75 = 12resize() 做了什么
- 创建新数组（容量翻倍，如 16 → 32）
- 重新计算每个元素的桶位置
- 将节点迁移到新数组
扩容后元素位置的计算技巧
旧数组容量 oldCap = 16（0b00010000）
新数组容量 newCap = 32（0b00100000）
对于每个元素，只需判断：
hash & oldCap == 0 → 新位置 = 原位置
hash & oldCap != 0 → 新位置 = 原位置 + oldCap
示例：
hash = 31（0b00011111），31 & 16 = 0 → 新位置不变
hash = 47（0b00101111），47 & 16 = 16 → 新位置 = 原位置 + 16这叫 "高位分流"：利用 hash 的高位（第 oldCap 那位）决定去留。
红黑树：解决链表过长的性能退化
何时转红黑树
链表长度 ≥ 8 且 数组长度 ≥ 64 → 转红黑树
红黑树节点数 ≤ 6 → 转回链表为什么是 8 和 6
这是 JDK 作者根据泊松分布计算的结果：
- 负载因子 0.75 时，链表长度达到 8 的概率极低（~0.00000006）
- 超过 8 说明哈希分布极差，需要用红黑树优化查找
- 6 是留的缓冲，避免在临界点反复转换
红黑树的查找
红黑树是自平衡二叉搜索树，查找路径长度不超过 O(log n)：
假设有 1000 个节点：
链表查找：最多 1000 次比较
红黑树查找：最多 ~10 次比较数据结构演进图
JDK 1.7 之前：
┌─────────┬─────────┬─────────┬─────────┐
│ bucket 0│ bucket 1│ bucket 2│ bucket 3│
│ [E1] │ [E2] │ [E3] │ [E4] │
│ ↓null │ [E5] │ ↓null │ ↓null │
└─────────┴─────────┴─────────┴─────────┘
链表解决冲突（头插法，并发问题）
JDK 1.8+：
┌─────────┬─────────┬─────────┬─────────┐
│ bucket 0│ bucket 1│ bucket 2│ bucket 3│
│ [E1] │ [E2] │ [E3] │ [E4] │
│ ↓null │ [E5] │ ↓null │ ↓null │
└─────────┴─────────┴─────────┴─────────┘
链表（≤8 个节点）或红黑树（>8 个节点）
桶内节点少 → 链表（开销小）
桶内节点多 → 红黑树（查找快）线程安全性
HashMap 是非线程安全的：
java
// ❌ 并发不安全
HashMap<Integer, Integer> map = new HashMap<>();
// ✅ ConcurrentHashMap
ConcurrentHashMap<Integer, Integer> safe = new ConcurrentHashMap<>();总结
| 要点 | 说明 |
|---|---|
| 底层结构 | 数组 + 链表（JDK 1.7）或数组 + 链表/红黑树（JDK 1.8+） |
| 哈希函数 | (h = key.hashCode()) ^ (h >>> 16) 混合高低位 |
| 索引计算 | (n - 1) & hash，等价于 hash % n |
| 扩容 | 容量翻倍，高位分流确定新位置 |
| 红黑树 | 链表长度 ≥ 8 且数组 ≥ 64 时转换，查找 O(log n) |
| 线程安全 | 非安全，生产用 ConcurrentHashMap |
一句话：HashMap 是「数组定位桶 + 链表/红黑树解决冲突 + 自动扩容」的组合设计。