HashMap 作为 Java 集合框架中最常用的键值对存储实现，几乎是所有 Java 开发者日常开发的 “标配”。但你真的了解它的底层逻辑吗？为什么 JDK 1.8 要引入红黑树？扩容时的高低位分离有什么优势？本文将从数据结构、核心算法、关键方法到性能优化，全方位拆解 HashMap 的设计精髓。
一、底层数据结构：从 “数组 + 链表” 到 “数组 + 链表 + 红黑树”
HashMap 的性能核心依赖于底层数据结构的设计，JDK 1.7 到 1.8 的演进是其性能跃升的关键。
1.1 JDK 1.7 vs 1.8 核心差异
| 特性 |
JDK 1.7 |
JDK 1.8 |
| 底层结构 |
数组 + 链表 |
数组 + 链表 + 红黑树 |
| 链表插入方式 |
头插法（易死循环） |
尾插法（避免死循环） |
| 扩容链表处理 |
重新计算 Hash，顺序混乱 |
高低位分离，保持原有顺序 |
| 性能优化 |
无 |
链表转红黑树（阈值 8） |
1.2 核心结构定义
HashMap 的底层由哈希桶数组、链表节点、红黑树节点三部分组成（JDK 1.8）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
transient Node<K,V>[] table;
transient int size;
int threshold;
final float loadFactor;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
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;
boolean red;
}
}
|
1.3 结构可视化
一、整体结构总览（HashMap 核心形态）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| +-------------------------- 哈希桶数组 (table) -------------------------+
| 下标0 | 下标1 | 下标2 | 下标3 | 下标4 | 下标5 | ... | 下标15 (默认容量) |
+-------+-------+-------+-------+-------+-------+-----+----------------+
| | |
| | v
| | +----------+ +----------+ +----------+
| | | 链表节点 | -> | 链表节点 | -> | 红黑树头 | -> 红黑树节点...
| | +----------+ +----------+ +----------+
| v
| +----------+
| | 空 (null) |
| +----------+
v
+----------------+
| 红黑树节点 (根) | -> 红黑树子节点...
+----------------+
|
二、哈希算法：如何精准定位元素？
HashMap 能实现 O (1) 级别的查询，核心依赖哈希值计算和索引定位的高效设计。
2.1 完整 Hash 计算流程
1
2
3
4
5
6
|
int h = key.hashCode();
h = h ^ (h >>> 16);
int index = h & (table.length - 1);
|
2.2 扰动函数的核心作用
JDK 1.8 内置的扰动函数：
1
2
3
4
| static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
|
为什么需要扰动？
- 原始 HashCode 是 32 位整数，数组长度通常较小（如 16），直接取模会导致==仅低位参与运算，冲突率极高；==
- 扰动函数将 HashCode 的==高 16 位与低 16 位异或==，让高位特征也参与索引计算，分布更均匀。
扰动效果对比
| 步骤 |
无扰动函数 |
有扰动函数 |
|
| 原始 Hash |
1111 1111 0000 0001 |
1111 1111 0000 0001 |
|
| 数组长度 - 1 |
0000 1111 1111 1111 (1023) |
0000 1111 1111 1111 (1023) |
|
| 最终索引 |
0000 0000 0000 0001 (1) |
0000 1111 0000 0000 (256) |
|
2.3 哈希冲突示例
某些 Key 的 HashCode 经过扰动后仍会落在同一桶，形成链表：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public class HashCollisionDemo {
public static void main(String[] args) {
String key1 = "Aa";
String key2 = "BB";
String key3 = "C#";
System.out.println("key1 hash: " + hash(key1));
System.out.println("key2 hash: " + hash(key2));
System.out.println("key3 hash: " + hash(key3));
}
static int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
}
|
三、核心方法：put () 的完整执行链路
put方法是时序图:
put () 是 HashMap 最复杂的方法，涵盖了初始化、冲突处理、扩容、树化等核心逻辑：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| 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;
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 != null && 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);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
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 () 核心步骤总结
- 计算 Key 的 Hash 值，定位哈希桶；
- 桶为空 → 直接插入新节点；
- 桶非空 → 匹配首节点 / 红黑树 / 链表；
- 链表长度≥8 → 转红黑树；
- 元素数超阈值 → 扩容。
四、扩容机制：resize () 的优化设计
扩容时序图:
扩容是 HashMap 性能的关键环节，JDK 1.8 对其做了大幅优化。
4.1 扩容核心逻辑
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
else if (oldThr > 0)
newCap = oldThr;
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
do {
Node<K,V> 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);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
|
4.2 高低位分离的优势
- 无需重新计算 Hash：仅通过
hash & oldCap 判断节点归属，效率提升；
- 保持链表顺序：避免 JDK 1.7 头插法导致的死循环；
- 负载更均衡：节点均匀分布在原索引和新索引，减少冲突。
五、性能优化：链表与红黑树的转换
当链表长度超过阈值（8）且数组容量≥64 时，HashMap 会将链表转为红黑树，将查询时间复杂度从 O (n) 降至 O (log n)。
5.1 核心阈值
1
2
3
4
5
6
|
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
|
5.2 链表转红黑树流程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null) hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
|
六、读取元素：get () 方法逻辑
get () 方法是 put () 的逆过程，逻辑更简洁：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| 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;
}
|
七、性能调优与最佳实践
理解底层原理后，合理使用 HashMap 能大幅提升程序性能。
7.1 合理设置初始容量
预估元素数量，避免频繁扩容（公式：初始容量 = 预估数量 / 负载因子 + 1）：
1
2
3
4
5
6
7
|
Map<String, User> badMap = new HashMap<>();
int expectedSize = 1000;
int initialCapacity = (int) (expectedSize / 0.75f) + 1;
Map<String, User> goodMap = new HashMap<>(initialCapacity);
|
7.2 选择合适的负载因子
| 负载因子 |
扩容频率 |
空间利用率 |
冲突概率 |
适用场景 |
| 0.5 |
高 |
低 |
低 |
空间充足、追求低冲突 |
| 0.75 |
中 |
中 |
中 |
通用场景（默认） |
| 1.0 |
低 |
高 |
高 |
空间敏感、查询频率低 |
7.3 避免使用可变对象作为 Key
Key 的 HashCode 若发生变化，会导致无法找到对应值：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class BadKey {
private String id;
public void setId(String id) { this.id = id; }
@Override
public int hashCode() { return id.hashCode(); }
}
class GoodKey {
private final String id;
public GoodKey(String id) { this.id = id; }
@Override
public int hashCode() { return id.hashCode(); }
}
|
7.4 线程安全选型
| 特性 |
HashMap |
Hashtable |
ConcurrentHashMap |
| 线程安全 |
❌ 否 |
✅ 是（全表锁） |
✅ 是（分段锁 / CAS） |
| null 键 / 值 |
✅ 支持 |
❌ 不支持 |
✅ 支持（JDK 1.8） |
| 性能 |
高 |
低 |
高 |
| 推荐场景 |
单线程 |
不推荐 |
多线程 |
八、核心要点总结
- 数据结构：JDK 1.8 引入红黑树，解决链表过长导致的查询性能下降问题；
- 哈希算法：扰动函数让高位参与索引计算，降低冲突率；与运算代替取模，提升性能；
- 扩容优化：高低位分离避免重新计算 Hash，尾插法解决死循环问题；
- 性能调优：预估初始容量、选择合适负载因子、使用不可变 Key 是核心最佳实践。
HashMap 的设计充分体现了 “空间换时间” 的思想，理解其底层原理不仅能帮你写出更高效的代码，也能在面试和问题排查中占据优势。希望本文能让你对 HashMap 有更深入的理解！
微信
支付宝