Java HashMap 原理剖析
1. 核心工作原理
Section titled “1. 核心工作原理”HashMap 的底层结构基于数组，并结合链表与红黑树来处理哈希冲突。其核心工作原理主要包含以下三点：
-
数据存储： 存入键值对时，系统先计算 Key 的
hashCode，再通过(table.length - 1) & hash的位运算，快速定位其在数组中的下标位置。 -
冲突解决： 当不同 Key 映射到同一位置时即产生哈希冲突。HashMap 默认通过链表将冲突元素串联；JDK 8 对此引入优化，若单一桶位的链表节点数超过 8 个且数组总长度达到 64，链表会自动转化为红黑树，从而将查找时间复杂度从 O(n) 优化至 O(log n)。
-
扩容机制：由于数组容量有限，HashMap 设定了默认值为 0.75 的负载因子。当空间占用达到 75% 时会触发自动扩容，将数组容量翻倍并重新分配所有数据的位置（rehash）。因该操作性能开销较大，建议在初始化时提前配置合理的预估容量。
HashMap 整体结构(JDK 1.8+):
table 数组(桶数组) ┌────────────────┐ index 0│ null │ ├────────────────┤ index 1│ Node ─▶ Node ─▶ Node ─▶ null (链表,长度 < 8) ├────────────────┤ index 2│ null │ ├────────────────┤ index 3│ TreeNode │ │ │ │ │ [红黑树] │ (链表长度 ≥ 8 且数组长度 ≥ 64 转树) │ / \ │ │ ... ... │ ├────────────────┤ index n│ null │ └────────────────┘Node 节点结构:
static class Node<K,V> implements Map.Entry<K,V> { final int hash; // key 的哈希值(扰动后) final K key; // 键 V value; // 值 Node<K,V> next; // 指向下一个节点(链表)}2. 哈希函数与扰动
Section titled “2. 哈希函数与扰动”2.1. 为什么需要扰动
Section titled “2.1. 为什么需要扰动”直接使用 key.hashCode() 的结果来取模定位下标会有问题: 数组容量通常不大(初始 16),只有哈希值的低几位参与运算,高位完全没用上,容易造成碰撞。
假设 key 的 hashCode = 0x7F8A_B1C2
table 容量 n = 16,计算下标:(n - 1) & hash = 0x0F & 0x7F8AB1C2 ─┬─ │ 只有最低 4 位参与运算 高 28 位完全被浪费2.2. 扰动函数实现
Section titled “2.2. 扰动函数实现”HashMap 通过将 hashCode 的高 16 位与低 16 位异或,让高位也参与运算:
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}扰动过程示意:
hashCode: 1111 0001 0110 1010 1100 0011 0101 1001 (高 16 位) (低 16 位)
右移 16 位: 0000 0000 0000 0000 1111 0001 0110 1010
两者异或: 1111 0001 0110 1010 0011 0010 0011 0011 ───────────────── 低 16 位融合了高位信息
→ 再与 (n-1) 做与运算定位下标时,低位包含了原始高位的分布特征,冲突概率显著降低2.3. 为什么容量必须是 2 的幂
Section titled “2.3. 为什么容量必须是 2 的幂”HashMap 强制要求容量 n 为 2 的幂次方,这样 (n - 1) 的二进制全是 1,可以用位与运算替代取模:
n 是 2 的幂时: hash % n 等价于 hash & (n - 1)
位与运算比取模快得多(取模底层是除法): n = 16 → n-1 = 0000 1111 → 保留 hash 低 4 位 n = 32 → n-1 = 0001 1111 → 保留 hash 低 5 位 n = 64 → n-1 = 0011 1111 → 保留 hash 低 6 位4. put 操作流程
Section titled “4. put 操作流程”put(key, value) 完整流程:
│ ▼ 计算 hash = hash(key) (扰动函数处理) │ ▼ table 是否已初始化? │ ├── 否 ──▶ resize() 初始化(默认容量 16) │ ▼ 计算下标 i = (n - 1) & hash │ ▼ table[i] 是否为空? │ ├── 是 ──▶ 直接新建 Node 放入,结束 │ ▼ 遍历 table[i] 位置的节点 │ ├── 发现 key 已存在(hash 相同 && equals 相同) ──▶ 覆盖旧 value,返回旧值 │ ├── 该位置是红黑树 ──▶ 按树节点逻辑插入 │ └── 该位置是链表 ──▶ 尾插法追加新节点 │ ▼ 链表长度 ≥ 8 且数组长度 ≥ 64? │ ├── 是 ──▶ 链表转红黑树(treeifyBin) └── 否 ──▶ 保持链表(或触发扩容) │ ▼ size++,检查是否超过阈值(threshold) │ ├── 超过 ──▶ resize() 扩容 └── 未超过 ──▶ 结束关键判定:key 相等的双重判断
// 找到已存在的 key 必须同时满足:if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))先比 hash(快速过滤),再比 == 或 equals(精确判定)。这也是为什么重写 equals 必须同时重写 hashCode——否则会出现 equals 相等但 hash 不同,无法正确命中已有 key。
5. 链表转红黑树
Section titled “5. 链表转红黑树”5.1. 为什么引入红黑树
Section titled “5.1. 为什么引入红黑树”JDK 1.7 只用数组 + 链表,极端情况下(大量冲突)链表会很长,查找退化为 O(N)。JDK 1.8 引入红黑树,将最坏情况下的查找优化到 O(log N)。
链表 vs 红黑树查找性能:
链表查找 10 个元素中的目标: A ──▶ B ──▶ C ──▶ D ──▶ E ──▶ F ──▶ G ──▶ H ──▶ I ──▶ J 最坏需要遍历全部 10 次,O(N)
红黑树查找: E / \ C H / \ / \ B D G I 最坏 log2(10) ≈ 4 次,O(log N)5.2. 转换条件
Section titled “5.2. 转换条件”链表转红黑树需要同时满足两个条件: ① 链表长度 ≥ 8 (TREEIFY_THRESHOLD) ② 数组长度 ≥ 64 (MIN_TREEIFY_CAPACITY)
只满足 ① 不满足 ② ──▶ 优先扩容(扩容后冲突会减少),而不是转树为什么阈值是 8: 理想哈希分布下(泊松分布),一个桶中链表长度达到 8 的概率约为 千万分之六,极低。设置为 8 是在空间和时间上的平衡——链表短时用链表更省空间,长到 8 说明哈希分布已经异常糟糕,值得用树结构换查找性能。
5.3. 红黑树退化回链表
Section titled “5.3. 红黑树退化回链表”当扩容或删除元素导致树节点数 ≤ 6(UNTREEIFY_THRESHOLD)时,红黑树会退化回链表。设置为 6 而不是 7,是为了避免在 7 和 8 之间频繁来回转换。
6. 扩容机制(resize)
Section titled “6. 扩容机制(resize)”6.1. 何时扩容
Section titled “6.1. 何时扩容”扩容触发条件: size > threshold (阈值 = 容量 × 负载因子)
默认配置: 初始容量 = 16 负载因子 = 0.75 初始阈值 = 16 × 0.75 = 12
→ 当 HashMap 中元素数量达到 12 时,触发扩容6.2. 为什么负载因子是 0.75
Section titled “6.2. 为什么负载因子是 0.75”负载因子(load factor)是空间与时间的权衡:
因子过小(如 0.5): ├── 优点:冲突少,查找快 └── 缺点:数组利用率低,浪费内存,扩容频繁
因子过大(如 1.0): ├── 优点:内存利用率高 └── 缺点:冲突概率大,查找性能下降
0.75 是经过数学推导和工程验证的经验值: → 冲突概率可接受,空间利用率也合理6.3. 扩容过程
Section titled “6.3. 扩容过程”扩容步骤:
① 新建一个容量为旧表 2 倍的新数组 oldCap = 16 ──▶ newCap = 32 oldThr = 12 ──▶ newThr = 24
② 遍历旧数组,将每个桶中的元素重新分布到新数组 │ ▼③ JDK 1.8 的巧妙优化:不用重新计算 hash,直接通过一位判断去留
由于新容量是旧容量的 2 倍,(n-1) 的掩码多了最高一位 只需看 key 的 hash 在这一位是 0 还是 1:
hash & oldCap == 0 ──▶ 元素留在原位置 i hash & oldCap != 0 ──▶ 元素迁移到新位置 i + oldCap扩容迁移示意:
扩容前(容量 16): index 5: Node(hash=5) ──▶ Node(hash=21) ──▶ Node(hash=37)
hash & 16(新增的那一位): 5 & 16 = 0 ──▶ 原位置 index 5 21 & 16 = 16 ──▶ 新位置 index 5 + 16 = 21 37 & 16 = 0 ──▶ 原位置 index 5
扩容后(容量 32): index 5: Node(hash=5) ──▶ Node(hash=37) index 21: Node(hash=21)7. 线程安全问题
Section titled “7. 线程安全问题”HashMap 在并发场景下存在多个隐患:
HashMap 并发问题:
① 数据覆盖 线程 A 和 B 同时对同一个桶执行 put,可能一方的数据被另一方覆盖 │ ▼ 线程 A: 发现 table[i] 为空,准备插入 线程 B: 同一时刻也发现 table[i] 为空,也准备插入 → 最终只有一个线程的数据保留,另一个丢失
② size 不准确 size++ 不是原子操作,多线程下计数错误
③ 扩容时重复迁移或数据丢失 多线程同时触发 resize,可能导致迁移不完整
④ JDK 1.7 特有:环形链表导致 CPU 100% 并发扩容时头插法形成环,get 操作陷入死循环8. 常见问题与最佳实践
Section titled “8. 常见问题与最佳实践”8.1. 初始容量建议预估
Section titled “8.1. 初始容量建议预估”如果已知最终要存放的数据量,建议指定初始容量以避免多次扩容:
// 要存放约 100 个元素,默认初始容量 16 会触发多次扩容Map<String, Object> map = new HashMap<>();
// 推荐:按 需要的容量 / 负载因子 + 1 计算// 100 / 0.75 + 1 ≈ 134,HashMap 内部会取整为 256Map<String, Object> map = new HashMap<>(134);
// 更精确:直接给出 2 的幂Map<String, Object> map = new HashMap<>(256);8.2. key 对象的要求
Section titled “8.2. key 对象的要求”作为 HashMap 的 key,对象必须满足:
① 重写 hashCode():保证同一对象每次返回相同值② 重写 equals():用于冲突时精确判定是否为同一 key③ hashCode 与 equals 一致:equals 相等的对象 hashCode 必须相等④ 推荐 key 不可变(如 String):避免 put 后修改导致 hashCode 变化,永久丢失
反例:用可变对象做 key User u = new User(1, "Alice"); map.put(u, "value"); u.setId(2); // 修改后 hashCode 变了 map.get(u); // 返回 null,数据"丢失"8.3. null 的处理
Section titled “8.3. null 的处理”HashMap 允许 null key 和 null value: null key 的 hash 固定为 0 ──▶ 存储在 table[0] 位置
对比: HashMap ──▶ 允许 null key 和 null value ✅ Hashtable ──▶ 不允许,put(null, x) 抛 NullPointerException ConcurrentHashMap ──▶ 不允许,避免歧义(get 返回 null 无法区分"不存在"和"值是 null")9. 关键参数速查表
Section titled “9. 关键参数速查表”| 参数 | 默认值 | 含义 |
|---|---|---|
DEFAULT_INITIAL_CAPACITY | 16 | 默认初始容量 |
MAXIMUM_CAPACITY | 2³⁰ | 最大容量 |
DEFAULT_LOAD_FACTOR | 0.75 | 默认负载因子 |
TREEIFY_THRESHOLD | 8 | 链表转红黑树的链表长度阈值 |
UNTREEIFY_THRESHOLD | 6 | 红黑树退化回链表的节点数阈值 |
MIN_TREEIFY_CAPACITY | 64 | 触发链表转树所需的最小数组容量 |
10. 原理总览
Section titled “10. 原理总览”┌──────────────────────────────────────────────────────────┐│ HashMap 高性能来源 ││ ││ put(key, value) ││ │ ││ ▼ ││ 扰动函数 hash() ──▶ (n-1) & hash 定位下标 ││ │ │ ││ │ 数组 O(1) 直接寻址 ││ │ │ ││ ▼ ▼ ││ 处理冲突: ││ ├── 链表(短) ──▶ 尾插法,O(N) 但 N 很小 ││ └── 红黑树(长) ──▶ O(log N) 防止退化 ││ │ ││ ▼ ││ 超过阈值 ──▶ 2 倍扩容,重新分布(利用位运算快速迁移) │└──────────────────────────────────────────────────────────┘| 机制 | 解决的问题 | 收益 |
|---|---|---|
| 数组 + 哈希寻址 | 快速定位 | O(1) 下标计算 |
| 扰动函数 | 哈希分布不均 | 减少碰撞,高位参与运算 |
| 2 的幂容量 | 取模慢 | 位与运算替代,速度提升 |
| 链表 + 红黑树 | 冲突退化 | 最坏情况 O(log N) 保底 |
| 动态扩容 | 冲突随数据增长加剧 | 负载因子控制,摊销成本 O(1) |
| 扩容位运算优化 | 重新 hash 昂贵 | 一位判定去留,无需重算 |