HashMap

kfkfka🍀zkye2025/3/1...大约 16 分钟

HashMap

Java8为什么将HashMap的插入方法改为了尾插法

参考链接：https://zhuanlan.zhihu.com/p/624141287
HashMap 在 Java7 -> Java8的变化：简单说明见文章

什么是 Hash 碰撞？怎么解决哈希碰撞？

Java 中 ConcurrentHashMap 1.7 和 1.8 之间有哪些区别？

让你设计一个 HashMap，你会怎么设计？

什么是Java的CAS（Compare-And-Swap）操作？

🌟JDK1.8将HashMap 头插法改尾插法，为何？

为什么说 hashmap 尾插法使得链表元素的插入顺序与元素插入的顺序一致，从而方便了元素的查找和遍历操作，提高了HashMap的查询效率？

因为它在实际的物理硬件上运行时，能带来额外的好处，主要是提升CPU缓存的命中率。

什么是CPU缓存？

CPU 访问内存的速度远慢于其自身的计算速度。为了弥补这个差距，CPU 内置了高速缓存（Cache）。当 CPU 需要数据时，它会先把内存中一块连续的数据加载到缓存里。如果下一个要访问的数据也在这块缓存中（即“缓存命中”），速度就会极快。如果不在（即“缓存未命中”），就需要重新去主内存读取，速度会慢几个数量级。

“顺序保持”如何利用缓存？

场景: 我们的旧链表在内存中是这样排列的：节点A -> 节点B -> 节点C。因为它们是按顺序插入的，它们在内存中的物理地址很可能是邻近的。
读取过程: CPU 开始遍历这个链表，当它读取节点 A 时，很可能会把节点 B 和节点 C 也预加载进高速缓存中（这被称为缓存的“空间局部性”原理）。
写入过程 (尾插法 / 顺序保持):
1. 处理 A，放入 low 链。
2. 处理 B，放入 high 链。
3. 处理 C，追加到 low 链的尾部（即 A 的后面）。
  这个写入过程基本是顺序的。它按照从头到尾的顺序处理节点，并将它们顺序地链接到新链表中。这种线性的、可预测的内存访问模式，非常符合 CPU 缓存的工作方式，因此缓存命中率高。

“顺序反转”（头插法）如何破坏缓存？

写入过程 (头插法 / 顺序反转):
1. 处理 A，放入 low 链。此时 low 链是 A。
2. 处理 B，放入 high 链。
3. 处理 C，头插入 low 链。这时需要修改 low 链的头指针，让 C 指向 A。
  这个过程需要来回跳转。当处理 C 时，它可能需要重新访问之前已经处理过的 A 节点来修改指针。如果 A 节点的信息已经被踢出缓存，就会导致一次“缓存未命中”，从而降低了实际运行速度。

为什么说 hashmap 尾插法可以使得链表长度比较平衡，减少了某些链表长度过长的情况？

🧩 前提：什么是“链表长度不平衡”？

在 HashMap 中，当多个键值对映射到同一个桶（bucket）时，它们会以链表的形式存储在这个桶中。理想情况下：

所有桶中的链表长度应该大致相等（即数据分布均匀）。
如果某些桶的链表特别长，而其他桶是空的或很短，就说明数据分布不均，称为“链表长度不平衡”。

这会导致：

查询效率下降（O(n)）
插入、删除操作变慢
极端情况可能退化为单链表

🤔 尾插法如何帮助链表长度更平衡？

✅ 关键在于扩容时的迁移策略

在 JDK 8 中，使用尾插法后，扩容时节点在新数组中的位置要么保持原索引，要么是原索引 + oldCap，这个特性被称为“高位低位拆分”（High-Low Index Splitting），是 HashMap 实现高效扩容的关键机制之一。

🔢 简要解释扩容机制（JDK 8）

假设原来的容量是 oldCap = 16，扩容后变为 newCap = 32。

每个键的 hash 对应的索引是：

index = hash & (capacity - 1)

扩容后：

新索引 = hash & (newCap - 1)
因为 newCap 是 oldCap 的两倍，所以 (newCap - 1) 比 (oldCap - 1) 多了一位二进制高位。

于是：

如果 hash 的这一位是 0，则新索引 = 原索引
如果 hash 的这一位是 1，则新索引 = 原索引 + oldCap

这样，一个桶中的链表会被分成两个部分：

高位为 0 的留在原位置
高位为 1 的迁移到新位置

💡 尾插法的作用：保留链表顺序，避免重新遍历

由于尾插法保证了链表顺序与插入顺序一致，在扩容迁移过程中，我们可以：

直接将链表分成两个子链表（高、低位链表）
不需要反转或重新排序
一次性完成迁移，效率更高

这就意味着：

同一个桶中的元素被平均分配到两个不同的桶中
链表长度整体上变得更短、更平衡

⚖️ 相比头插法的问题（JDK 7）

在 JDK 7 中采用头插法，扩容时需要：

从旧链表头部开始取节点
插入到新链表头部
导致链表顺序反转

这会带来两个问题：

破坏原始插入顺序，可能导致某些桶中集中了很多节点
在多线程下容易形成环形链表，导致查询死循环

而尾插法解决了这些问题，使扩容后的链表分布更加均衡。

📊 总结：尾插法为何能提升链表平衡性

特性	影响
扩容时按高位拆分	自然地将链表分为两部分，实现负载均衡
尾插法保留顺序	避免链表反转，便于快速迁移
分裂成高低链表	减少单个桶中链表长度，提升查找效率
更加稳定和安全	避免多线程下的链表成环问题

✅ 结论

尾插法本身不会直接让链表更平衡，但配合 JDK 8 的扩容策略（高位拆分）和链表分裂机制，可以让扩容后的链表长度更均匀，从而减少某些链表过长的情况。

这是 HashMap 在性能、并发、稳定性方面的重要优化之一。

为什么 java8 中的尾插法可以一次性完成迁移，而 java7 中需要单独计算每个元素 hash？java7 中能不能也一次性迁移，或者将 java8 中的尾插法改为头插法可以保持一次性迁移吗？

Java 8 能够实现“一次性完成链表迁移”，不是因为尾插法本身，而是因为尾插法配合 hash 高位拆分策略，使得链表结构在扩容时仍然保持可预测性和一致性。

为什么 java8 中的尾插法可以一次性完成迁移，而 java7 中需要单独计算每个元素 hash？
答案是理论上可以，只是实际实现上没有这么做，java8中的高位拆分方式其实是一种数学上的优化，本质上并不是新的扩容方法（即优化了过程，结果相同），java7 中的相应部分完全可以替换为类似实现。
假如 Java 8 改为头插法，还能一次性迁移吗？
可以，但会失去保证顺序的优点，从而重新引入环形链表的风险。顺序性和避免环形链表风险才是改头插为尾插的关键，一次性迁移只是算法上的优化，头插也行。

什么是“hash 高位拆分策略”？

这里的高位指的是 hash 值中的最高位；在 Java 8 的 HashMap 中，高位拆分策略（High-Low Index Splitting） 是一种 高效的扩容迁移机制。它利用了哈希值的二进制特性和数组容量为 2 的幂的特点。

这是不是也是 HashMap 选择容量大小为 2^n 的原因之一呢？

🧮 原理简述：

假设当前数组长度是 oldCap = 16，那么 (oldCap - 1) 就是 0b1111，用于计算索引：

index = hash & (oldCap - 1);

当数组扩容一倍后变为 newCap = 32，(newCap - 1) = 0b11111。

这时：

新索引 = hash & (newCap - 1)
相比旧索引，多了一位高位（也就是原来的第 5 位）

我们可以用这一位来判断节点在新数组中的位置：

高位	新索引
0	原索引
1	原索引 + oldCap

这样就可以把一个桶里的链表分成两个子链：

低位链表（low链）：保留在原索引位置
高位链表（high链）：迁移到 原索引 + oldCap 位置

上述的过程可以优化为：

// 简化后的源码逻辑
if ((node.hash & oldCap) == 0) {
    // 如果结果为0，说明hash值的第5位是0。
    // 那么它的新索引与旧索引完全相同，元素位置不变。
} else {
    // 如果结果不为0，说明hash值的第5位是1。
    // 那么它的新索引就是“旧索引 + oldCap”，元素需要移动。
}

🌟这就是所说的“一次性迁移”的本质：对于原哈希桶中的一串元素（链表或红黑树），HashMap不再需要为每个元素重新计算一遍完整的哈希和索引。它只需遍历一次，根据每个元素的哈希值的特定位是0还是1，就能将它们高效地拆分到两个新的位置上。(在 java7 的实现中都是重新完整计算一遍)

现在，我们回到最初的“高位拆分策略”（扰动函数）。它的作用在这里就体现出来了。

hash = key.hashCode() ^ (key.hashCode() >>> 16)

这个操作将原始哈希码的高16位与低16位进行了异或，使得高位的特征影响了低位。

这有什么用呢？

想象一下，如果没有这个扰动函数，而我们恰好有一批对象的hashCode()实现得不好，它们的值可能很接近，只在高位有区别。

没有扰动：在扩容到32时，需要判断哈希值的第5位。如果这批对象的哈希值第5位都恰好是0，那么扩容时，原来挤在一个桶里的所有元素，会原封不动地被迁移到新表的同一个桶里。扩容完全没有起到打散元素、缓解冲突的作用！
有了扰动：高位的差异通过^ (h >>> 16)操作，被“传递”到了低位。这使得最终的hash值的每一位（包括决定扩容位置的第5位）都变得更加随机和均匀。这样，当扩容发生时，原来在一个桶里的元素，就有大约一半的概率第5位是0（留在原位），一半的概率是1（移动到新位）。

在探讨HashMap的实现原理时，一个经常被提及但又略显神秘的概念是所谓的“高位拆分策略”。这个听起来颇为专业的术语，实际上并非官方命名，而是对HashMap内部为了优化哈希冲突、提升性能而采用的一种关键技术的形象描述。其核心在于HashMap的扰动函数（Perturbation Function），它通过一系列位运算，将哈希值的高位信息“拆分”并混合到低位中，以确保哈希表中的元素分布更均匀。

为什么需要高位拆分（扰动）？

要理解高位拆分策略的必要性，首先需要了解HashMap是如何通过哈希值确定存储位置的。

获取哈希码：当向HashMap中存入一个键值对时，它首先会调用键（Key）对象的hashCode()方法，获取一个整型的哈希码。
计算索引：HashMap内部维护一个数组（桶，Bucket），为了将哈希码映射到这个数组的特定索引上，它会使用一个看似简单的位运算：(n - 1) & hash。其中，n是数组的长度，而hash是经过处理后的哈希码。

这里的关键在于，HashMap的数组长度n被设计为始终是2的幂次方。这个设计使得(n - 1)的二进制表示会是一个低位全为1的掩码（例如，当n=16时，n-1=15，二进制为0000 1111）。因此，(n - 1) & hash这个操作实际上只会用到hash值的低位。

问题由此产生：如果两个不同的对象，它们的hashCode()返回值虽然不同，但低位部分恰好相同，那么它们在不经过任何处理的情况下，就会被映射到HashMap数组的同一个索引上，从而产生哈希冲突。如果大量的键都具有这种特性，就会导致某些桶中的链表（或红黑树）过长，严重影响HashMap的查询效率，使其时间复杂度从理想的 O(1) 退化到 O(logn) 甚至 O(n)。

高位拆分策略如何工作？

为了解决上述问题，HashMap的设计者引入了扰动函数。这个函数的目标是在计算索引之前，对原始的hashCode()进行一次“扰动”，将高位的特征混合到低位中，从而降低哈希冲突的概率。即使原始哈希值的低位相同，只要高位不同，经过扰动后，它们的最终哈希值也大概率会不同。

这个策略的具体实现方式在不同的Java版本中有所演变，但核心思想一致。

JDK 1.8中的实现

在Java 8及以后的版本中，HashMap的扰动函数非常简洁高效：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这行代码的含义是：

首先，获取键的原始哈希码h = key.hashCode()。
然后，将h无符号右移16位（h >>> 16），这样就得到了原始哈希码的高16位。
最后，将原始哈希码h与它的高16位进行**异或（XOR）**运算。

举例说明：

假设一个哈希码h的32位二进制表示为：

1111 0000 1111 0000 0000 1111 0000 1111

h >>> 16 的结果是：

0000 0000 0000 0000 1111 0000 1111 0000

两者进行异或运算后，得到新的哈希值。可以看到，原始哈希值的高16位（1111 0000 1111 0000）的特征通过异或操作，影响了最终结果的低16位。这样一来，即使有两个哈希码的低16位完全相同，但只要它们的高16位不同，经过扰动后，最终用于计算索引的哈希值也会有很大概率变得不同。

JDK 1.7中的实现

在JDK 1.7中，扰动函数更为复杂，进行了多次的异或和移位操作，旨在让哈希分布得更加混乱和均匀。

Java

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

虽然实现方式不同，但其根本目的与JDK 1.8是一致的：混合高位和低位的信息，减少因哈希函数实现不佳或特定数据集导致的哈希冲突。 JDK 1.8的实现则是在性能和混合效果之间取得了更好的平衡。

总结

“高位拆分策略”是HashMap内部一项精妙的优化，它并非真的将高位和低位“拆分”开，而是通过扰动函数，巧妙地利用位运算将高位的差异性传递并混合到决定数组索引的低位中。这一策略的核心价值在于：

降低哈希冲突：有效应对那些hashCode()实现质量不高，仅在低位区别不大的情况。
提升分布均匀性：使得键值对在HashMap的内部数组中分布得更加均匀，避免局部区域链表过长。
保障性能稳定：确保HashMap在各种数据模式下都能维持接近 O(1) 的高效性能。

因此，理解这一策略对于深入掌握HashMap的工作原理以及编写高效、健壮的Java应用程序至关重要。

示例说明：

假设有一个链表：

初始容量：oldCap = 4
扩容后容量：newCap = 8

它们的 hash 分别是：

A: hash = 0b1000（高位为 0）
B: hash = 0b1010（高位为 1）
C: hash = 0b0000（高位为 0）
D: hash = 0b1011（高位为 1）

若使用 尾插法
插入顺序：
```
插入 A → 插入 B → 插入 C → 插入 D
链表结构：A → B → C → D
```
扩容时：
根据每个节点的 hash 高位拆分为两个链表：
节点高位新索引位置
A 0 原索引
B 1 原索引 + oldCap
C 0 原索引
D 1 原索引 + oldCap
扩容 (resize) 过程:
1. 系统遍历这个 A → B → C → D 的链表。
2. 为 "low 链" 和 "high 链" 分别维护头指针（head）和尾指针（tail）。
3. 遍历 A: 高位为 0，放入 low 链。low 链: A。
4. 遍历 B: 高位为 1，放入 high 链。high 链: B。
5. 遍历 C: 高位为 0，追加到 low 链尾部。low 链: A → C。
6. 遍历 D: 高位为 1，追加到 high 链尾部。high 链: B → D。
拆分结果：
- low 链（高位为 0）：A → C
- high 链（高位为 1）：B → D
结果：
- low 链插入到原桶位置
- high 链插入到新桶位置（原索引 + oldCap）
- 迁移完成，无需重新计算每个 hash
若使用 头插法 （Java 7 及以前）
插入顺序：
```
插入 A → 插入 B → 插入 C → 插入 D
链表结构：D → C → B → A
```
扩容时：
由于链表顺序与插入顺序相反，hash 的高位分布被打乱：
节点高位新索引位置
D 1 原索引 + oldCap
C 0 原索引
B 1 原索引 + oldCap
A 0 原索引
扩容 (resize) 过程: Java 7 的实现方式比较直接，它不是像 Java 8 那样进行巧妙地拆分，而是：
1. 创建一个新的、容量翻倍的 table。
2. 遍历旧 table 中的每一个桶，再遍历桶中的每一个节点。
3. 对于每一个节点，重新计算它在新 table 中的索引位置 (index = hash & (newCap - 1))。
4. 将该节点以头插法插入到新 table 对应索引的链表中。
但此时链表顺序是 D → C → B → A，无法直接利用 hash 高位来划分出 low 和 high 链。
因此：
- 必须逐个 rehash
- 重新计算 index
- 重新插入到新链表头部
缺点：
- 无法一次性迁移
- 效率低
- 多线程下可能形成环形链表（死循环）

节点	高位	新索引位置
A	0	原索引
B	1	原索引 + oldCap
C	0	原索引
D	1	原索引 + oldCap

节点	高位	新索引位置
D	1	原索引 + oldCap
C	0	原索引
B	1	原索引 + oldCap
A	0	原索引

一个重要原因在于多线程环境下，尾插法可以一定程度上避免头插法时循环等待导致的死锁问题。

为什么头插法容易出现死锁？

首先，我们要明确 hashmap 在插入时需要判断 key 是否已经存在。