HashMap底层实现与源码分析
约 1864 字大约 6 分钟
javahashmap
2025-03-02
概述
HashMap 是Java中使用最广泛的Map实现,基于哈希表提供常数时间的 put/get 操作。从 Java 8 开始,其底层数据结构从「数组 + 链表」演进为「数组 + 链表 + 红黑树」,在哈希冲突严重时依然能保持良好性能。
数据结构总览
核心属性
public class HashMap<K,V> extends AbstractMap<K,V> {
// 默认初始容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表→红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
// 红黑树→链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 树化最小表容量(小于64时优先扩容而非树化)
static final int MIN_TREEIFY_CAPACITY = 64;
transient Node<K,V>[] table; // 桶数组
transient int size; // 键值对总数
int threshold; // 扩容阈值 = capacity × loadFactor
final float loadFactor; // 负载因子
transient int modCount; // 结构修改计数(fail-fast)
}Node节点结构
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 经过扰动函数处理的哈希值
final K key;
V value;
Node<K,V> next; // 链表后继
}
// 红黑树节点,继承自LinkedHashMap.Entry → Node
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent;
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // unlink时使用
boolean red;
}哈希函数(扰动函数)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}将高16位与低16位异或,使得高位信息也能参与索引计算,减少哈希碰撞。
桶位计算:index = hash & (table.length - 1)。因为 table.length 始终是2的幂,所以 length - 1 的二进制全为1,与运算等价于取模但效率更高。
put操作流程
源码简析
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;
// 1. 懒初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2. 桶位为空直接放入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 3. key完全匹配
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 4. 红黑树节点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 5. 链表遍历
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // 链表长度达到8
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 6. 存在旧值则替换
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // LinkedHashMap回调
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict); // LinkedHashMap回调
return null;
}扩容机制(resize)
核心规则:扩容为原来的2倍。对于旧桶中每个节点,只需判断 hash & oldCap 是0还是1:
- 0:留在原位
index - 1:移到新位
index + oldCap
这是 Java 8 的优化,避免了重新计算所有元素的索引。
// resize 中链表拆分的关键逻辑
Node<K,V> loHead = null, loTail = null; // 低位链表(留原位)
Node<K,V> hiHead = null, hiTail = null; // 高位链表(偏移oldCap)
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null) loHead = e;
else loTail.next = e;
loTail = e;
} else {
if (hiTail == null) hiHead = e;
else hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);树化与退化
| 条件 | 操作 |
|---|---|
| 链表长度 >= 8 且 table.length >= 64 | 链表 → 红黑树 |
| 链表长度 >= 8 且 table.length < 64 | 扩容(而非树化) |
| 树节点数 <= 6(扩容/删除后) | 红黑树 → 链表 |
为什么阈值是8? 根据泊松分布,在负载因子0.75下,单个桶中出现8个元素的概率约为 0.00000006,属于极端情况。树化机制是对极端碰撞的防御措施。
Java 7 vs Java 8 对比
| 特性 | Java 7 | Java 8 |
|---|---|---|
| 底层结构 | 数组 + 链表 | 数组 + 链表 + 红黑树 |
| 链表插入方式 | 头插法 | 尾插法 |
| 哈希函数 | 4次位运算 + 5次异或 | 1次位运算 + 1次异或 |
| 扩容链表迁移 | 反转顺序(并发致死循环) | 保持顺序 |
| 最坏查找 | O(n) | O(log n) |
线程安全问题
HashMap 不是线程安全的。并发操作可能导致:
- 数据丢失:两个线程同时 put 到同一个桶位,后者覆盖前者
- 死循环(Java 7):头插法扩容时链表成环,get 时无限循环
- size 不准确:
++size非原子操作
// 错误:多线程共享HashMap
Map<String, Integer> unsafeMap = new HashMap<>();
// 多线程同时put → 数据不一致
// 正确方案
Map<String, Integer> safeMap = new ConcurrentHashMap<>();
// 或
Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());常见面试FAQ
Q: 为什么容量必须是2的幂?
A: 桶位计算 hash & (n-1) 依赖于 n 是2的幂。这时 n-1 的二进制全为1,保证 hash 的低位都能参与索引计算,减少碰撞。若 n 不是2的幂,某些桶位永远无法被映射到。
Q: 为什么负载因子默认0.75?
A: 这是空间和时间的折中。0.75意味着平均每个桶有0.75个元素时触发扩容。值越大,空间利用率高但碰撞增多;值越小,碰撞少但浪费空间。0.75近似于log(2) ≈ 0.693,在数学上有较优的碰撞概率表现。
Q: HashMap允许null key吗?
A: 允许。null key 的 hash 固定为 0,始终存放在 table[0]。ConcurrentHashMap 不允许 null key/value。
Q: 如何正确设置初始容量?
A: 如果已知元素数量 n,设置 initialCapacity = (int)(n / 0.75) + 1 可以避免扩容开销。Guava 提供 Maps.newHashMapWithExpectedSize(n) 简化此操作。
性能调优参考
| 参数 | 默认值 | 调优建议 |
|---|---|---|
| initialCapacity | 16 | 预估元素数 / loadFactor + 1 |
| loadFactor | 0.75 | 一般无需调整 |
| 键对象 hashCode | — | 分布均匀,避免大量碰撞 |
总结
HashMap 是一个精心设计的数据结构,通过扰动函数减少碰撞、红黑树退化防御极端情况、尾插法消除并发死循环(Java 8)、高低位分流优化扩容效率。深入理解其实现,不仅能在面试中游刃有余,更能在实际开发中合理选型和调优。
贡献者
更新日志
9f6c2-feat: organize wiki content and refresh site setup于