深入剖析 HashMap：内部结构与性能优化
引言
HashMap 是 Java 集合框架中的核心类，广泛应用于数据存储和检索场景。本文将深入剖析其内部结构，包括数组、链表和红黑树的转换机制，帮助读者理解其工作原理和性能优化策略。
1. HashMap 的基本结构
1.1 数组（Array）
- 作用：存储桶（bucket），每个桶可存放一个或多个键值对
- 初始容量：默认 16，可通过构造函数自定义
- 扩容机制：当元素数量超过阈值（
capacity * loadFactor）时，数组扩容至原大小的两倍
1.2 链表（Linked List）
- 触发条件：桶中元素数量超过阈值（默认 8）时使用链表存储
- 特点：
- 插入/删除时间复杂度：O(1)
- 查找时间复杂度：O(n)
1.3 红黑树（Red-Black Tree）
- 触发条件：
- 链表长度 > 8
- 数组容量 ≥ 64
- 特点：
- 插入/删除/查找时间复杂度：O(log n)
2. 核心数据结构的使用
2.1 数组的索引计算
index = (n - 1) & hash
n：数组长度（容量）
hash：键的哈希值（通过扰动函数优化分布）
2.2 链表的实现
-
节点结构：
static class Node<K,V> {final int hash;final K key;V value;Node<K,V> next; } /** 后续在 Node<K,V> 使用时被transient修饰， transient是 Java 中的一个关键字，用于修饰类的成员变量。被 transient 修饰的变量表示该变量不会被默认的序列化机制所保存。 作用：阻止某个变量在对象序列化时被写入文件或传输。 使用场景：当某些数据不需要被持久化（如敏感信息、临时数据等），可以使用 transient。*/
2.3 红黑树的实现
-
节点结构：
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; }
3. 数据结构转换机制
3.1 链表 → 红黑树
条件：
-
链表长度 > 8
static final int TREEIFY_THRESHOLD = 8; -
数组容量 ≥ 64
static final int MIN_TREEIFY_CAPACITY = 64;
转换过程：
// jdk1.8
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);}
}
3.2 红黑树 → 链表
条件：树节点数量 ≤ 6
static final int UNTREEIFY_THRESHOLD = 6;
转换过程：
// jdk1.8
final Node<K,V> untreeify(HashMap<K,V> map) {Node<K,V> hd = null, tl = null;for (Node<K,V> q = this; q != null; q = q.next) {Node<K,V> p = map.replacementNode(q, null);if (tl == null)hd = p;elsetl.next = p;tl = p;}return hd;
}
4. 性能优化策略
4.1 哈希冲突优化
-
扰动函数：通过二次哈希分散键值对分布
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
4.2 容量设置策略
- 初始容量：预估存储量，避免频繁扩容
- 负载因子：默认 0.75，平衡时间与空间成本
4.3 扩容优化
- 增量迁移：扩容时逐步迁移节点，避免长时间阻塞
5. 总结
| 结构 | 触发条件 | 时间复杂度 | 适用场景 |
|---|---|---|---|
| 数组 | 基础存储结构 | O(1) 索引访问 | 元素均匀分布 |
| 链表 | 桶中元素 ≤ 8 | O(n) 查找 | 少量哈希冲突 |
| 红黑树 | 桶中元素 >8 且容量 ≥64 | O(log n) 操作 | 严重哈希冲突 |
关键点：
-
链表转树需同时满足长度和容量条件
-
树转链表采用更保守的阈值（6）防止频繁转换
-
合理的初始容量和负载因子可显著提升性能
