本文深入剖析Java HashMap：它是一个“数组+链表/红黑树”结构，利用哈希实现O(1)存取。核心机制包括扰动函数、高效扩容和链表转红黑树。容量为2的幂次方以使用位运算替代取模，是其性能关键。

我们来深入、系统地剖析一下HashMap的实现原理。为了真正地“深入理解”，我会从它的设计哲学、核心数据结构、关键操作流程、重要机制以及版本演进等多个角度进行拆解。

（以下分析主要基于 Java 8+ 的 HashMap 实现，因为这是目前最主流、最完善的版本）

一、HashMap 的设计哲学：空间换时间

HashMap 的核心目标是提供平均时间复杂度为 O(1) 的键值对（Key-Value）存取。

它是如何做到的呢？答案就是“空间换时间”。它通过创建一个相对较大的数组，利用哈希函数将任意的 Key 映射到数组的特定索引上，从而实现快速定位。理想情况下，如果每个 Key 都映射到不同的索引，那么存取操作就和访问数组元素一样快，即 O(1)。

当然，现实中不可避免地会出现哈希冲突（不同的 Key 映射到同一个索引），HashMap 的精髓就在于它如何高效地设计数据结构和处理流程来解决这些冲突。

二、核心数据结构 (Java 8+)

HashMap 的内部结构可以看作是 “数组 + 链表 / 红黑树” 的复合结构。

1. Node<K,V>[] table：数组

   • 这是 HashMap 的主体，也被称为哈希桶 (Hash Bucket)。
   • 数组的每一个元素都是一个桶，用于存放一个或多个键值对。
   • 如果一个桶里没有元素，那么它就是 null。
   • 如果一个桶里有元素，它通常是一个 Node 节点的引用。

2. Node<K,V>：链表节点

   • 这是构成链表的基本单元，它实现了 Map.Entry<K,V> 接口。
   • 每个 Node 对象包含四个核心信息：
     • final int hash: Key 的哈希值。这个值被缓存起来，避免重复计算。
     • final K key: 键。
     • V value: 值。
     • Node<K,V> next: 指向链表中的下一个节点。

3. TreeNode<K,V>：红黑树节点

   • 当一个哈希桶中的链表长度超过一个阈值（TREEIFY_THRESHOLD，默认为 8），并且数组的总容量（capacity）大于一个阈值（MIN_TREEIFY_CAPACITY，默认为 64）时，这个链表就会被转换成一个红黑树。
   • TreeNode 是 Node 的子类，它额外包含了红黑树所需的父、左、右子节点指针以及颜色属性。
   • 为什么要用红黑树？ 因为红黑树是一种自平衡的二叉查找树，它能保证在最坏情况下，查找、插入、删除的时间复杂度为 O(log n)，其中 n 是树中节点的数量。这远比链表的 O(n) 要高效，能有效防止哈希攻击（即构造大量哈希冲突的 Key，使 HashMap 性能退化）。

三、关键参数

• initialCapacity (初始容量)：哈希桶数组的初始大小，默认为 16。
• loadFactor (加载因子)：负载因子，默认为 0.75。它衡量了 HashMap 的填充程度。
• threshold (扩容阈值)：capacity * loadFactor。当 HashMap 中存储的元素数量（size）超过这个阈值时，就会触发扩容 (resize)。

四、核心操作流程详解

1. put(key, value) 方法

这是 HashMap 最复杂也是最核心的操作。

1. 计算哈希值：

   • 首先判断 key 是否为 null。HashMap 允许一个 null key，它总是被放在 table[0] 的位置。
   • 对于非 null 的 key，调用其 hashCode() 方法得到一个原始哈希码。
   • 为了减少哈希冲突，HashMap 会对原始哈希码进行二次哈希（或称扰动函数）：(h = key.hashCode()) ^ (h >>> 16)。将哈希码的高 16 位与低 16 位进行异或操作，这样高位的特征也能参与到最终的索引计算中，使得哈希分布更均匀。

2. 计算数组索引 (Index)：

   • 使用 (n - 1) & hash 来计算索引，其中 n 是数组的容量（capacity）。
   • 为什么用 & 而不是 %？ 因为当 n 是 2 的幂次方时，hash & (n - 1) 等价于 hash % n，但位运算 & 的效率远高于取模运算 %。这就是 HashMap 的容量总是 2 的幂次方的原因。

3. 在指定索引位置插入/更新数据：

   • Case A: 桶为空：如果 table[index] 是 null，直接创建一个新的 Node 节点并放入该位置。
   • Case B: 桶不为空（发生哈希冲突）：
     • i. 检查第一个节点：判断 table[index] 的 key 是否与要插入的 key 相同（通过 hash 值和 equals() 方法判断）。如果相同，直接更新 value 并返回旧值。
     • ii. 检查是树还是链表：如果第一个节点不是要找的 key，判断该节点是 TreeNode 还是 Node。
       • 如果是 TreeNode（红黑树）：调用红黑树的插入方法 (putTreeVal)。在树中查找或插入新节点，时间复杂度为 O(log n)。
       • 如果是 Node（链表）：遍历链表。
         • 在遍历过程中，如果找到一个 key 与要插入的 key 相同，则更新 value 并返回旧值。
         • 如果遍历到链表末尾仍未找到相同的 key，则在链表尾部插入一个新的 Node 节点（尾插法，Java 7 是头插法，多线程下易产生环形链表）。
     • iii. 链表转红黑树检查：在链表插入新节点后，检查该链表的长度是否达到了 TREEIFY_THRESHOLD (8)。如果达到了，并且数组总容量 capacity >= MIN_TREEIFY_CAPACITY (64)，则调用 treeifyBin() 方法将这个链表转换为红黑树。

4. 检查是否需要扩容：

   • 插入成功后，size（元素总数）会加 1。
   • 检查 size 是否大于 threshold（扩容阈值）。如果大于，则触发 resize() 方法。

2. get(key) 方法

get 的流程相对简单，是 put 流程的查找部分。

1. 计算 key 的哈希值和数组索引（与 put 方法完全相同）。
2. 定位到 table[index]。
3. 如果桶为空，直接返回 null。
4. 如果桶不为空：
   • 检查第一个节点的 key 是否匹配。如果匹配，返回其 value。
   • 如果不匹配，判断该桶是链表还是红黑树。
   • 链表：遍历链表，使用 equals() 逐个比较 key，找到则返回 value。
   • 红黑树：调用红黑树的查找方法，找到则返回 value。
5. 如果遍历完整个结构（链表或树）都未找到，返回 null。

五、关键机制：resize() 扩容

扩容是 HashMap 保持高性能的关键，但它本身也是一个耗时的操作。

1. 触发时机：当 size > threshold 时触发。

2. 扩容过程：

   • 创建一个新的数组，其容量是旧数组的两倍 (newCap = oldCap << 1)，阈值也变为两倍 (newThr = oldThr << 1)。
   • 遍历旧数组 oldTable 的每一个桶。
   • 将旧桶中的所有节点重新计算位置并迁移到新数组 newTable 中。

3. 迁移优化 (Java 8 的精髓)：

   • 在 Java 7 中，迁移需要对每个元素重新计算哈希和索引，效率较低。
   • 在 Java 8 中，利用了容量是 2 的幂次方的特性，做了一个非常巧妙的优化。
   • 一个桶中的元素在扩容后，只可能去两个位置：原索引位置 或 “原索引 + 旧容量” 的位置。
   • 判断依据是 (e.hash & oldCap) == 0。
     • oldCap 在二进制表示中只有一位是 1（例如，16 是 00010000）。
     • e.hash & oldCap 的结果是 0 还是 1，取决于 e.hash 在 oldCap 为 1 的那个位上是 0 还是 1。
     • 这恰好可以将一个旧桶中的链表（或树）完美地拆分成两个子链表（或子树）：一个 lo 链表（留在原索引）和一个 hi 链表（去新索引）。
   • 这样，整个迁移过程不再需要重新计算每个元素的 hash，只需一次 & 运算，然后将拆分后的两个子链表分别挂到新数组的对应位置即可，大大提高了 resize 的效率。

六、版本演进：Java 7 vs Java 8

七、总结

要深入理解 HashMap，你需要记住以下几个核心要点：

1. 数据结构：数组 + 链表 / 红黑树，是空间换时间的典范。
2. 哈希与索引：hashCode() + 扰动函数 -> & (capacity - 1) 计算索引。容量必须是 2 的幂次方是为了高效的位运算。
3. 冲突解决：拉链法是基础，引入红黑树是为了防止极端情况下的性能退化，将最坏时间复杂度从 O(n) 优化到 O(log n)。
4. 扩容机制 (resize)：由加载因子 (loadFactor) 控制触发时机。Java 8 的 resize 优化是关键，通过 (e.hash & oldCap) 将旧桶元素高效地拆分到新桶的两个可能位置。
5. 线程不安全：HashMap 的所有操作都不是线程安全的。在多线程环境中，应使用 ConcurrentHashMap。

掌握了这些，你对 HashMap 的理解就不仅仅停留在“它是一个存键值对的集合”，而是深入到了它的骨架、血肉和运行机制之中。

其中

为什么当 n 是 2 的幂次方时，位运算 & 的效率远高于取模运算 %

这是一个非常棒的问题，也是理解 HashMap 设计精髓的关键点之一。我们通过具体的例子和二进制来把它彻底讲清楚。

核心思想回顾

• 目标：将一个哈希值 hash 映射到数组索引 index 上，范围是 [0, n-1]，其中 n 是数组的容量。
• 方法1（取模）：index = hash % n
• 方法2（位运算）：index = hash & (n - 1)
• 前提：方法2成立的充要条件是 n 必须是 2 的幂次方。

第一部分：为什么它们等价？（以 n=16 为例）

当 n 是 2 的幂次方时，它在二进制表示中有个非常显著的特点：只有一位是 1，其余都是 0。

• n = 16
• 16 的二进制表示是：00010000

现在，我们来看 n - 1：

• n - 1 = 15
• 15 的二进制表示是：00001111

你发现了吗？n - 1 的二进制形式变成了一串低位连续的 1。这个 n-1 就像一个“低位掩码”或“低位过滤器”。

举例：计算 hash = 83 的索引

我们要把 hash = 83 存入容量为 16 的 HashMap 中。

83 的二进制表示是 01010011。

方法1：取模运算 (%)

83 % 16 = 3
因为 83 = 16 * 5 + 3。所以索引是 3。

方法2：位与运算 (&)

我们来计算 hash & (n - 1)，也就是 83 & 15。

  01010011   (这是 83)
& 00001111   (这是 15, 也就是 n-1)
-----------------
  00000011   (这是 3)

发生了什么？

• & (按位与) 运算的规则是：只有当两个操作数的对应位都是 1 时，结果的对应位才是 1，否则为 0。
• 因为 (n-1) 的高位都是 0，所以 hash 值的高位部分（0101）与 0000 进行 & 运算后，结果全部变成了 0。这相当于屏蔽了高位。
• 因为 (n-1) 的低位都是 1，所以 hash 值的低位部分（0011）与 1111 进行 & 运算后，结果保持了原来的值（因为 x & 1 = x）。
• 最终，hash & (n-1) 的结果就是取出了 hash 值的低位部分。

关键洞察：
对于一个 2 的幂次方 n（例如 16），一个数除以 n 的余数，完全由这个数的低位决定。具体来说，如果 n = 2^k (例如 16 = 2^4)，那么余数就由这个数的二进制表示的末尾 k 位决定。

在我们的例子中，n=16=2^4，所以余数由 83 的末尾 4 位决定。
83 的二进制 01010011，末尾 4 位是 0011，它的十进制值就是 3。

hash & (n-1) 这个操作，正是通过 n-1 这个 0...01...1 形式的掩码，精准地、高效地只保留了 hash 值的末尾 k 位，从而得到了和取模运算完全相同的结果。

第二部分：为什么位运算 & 远快于取模 %？

这要从计算机底层（CPU 指令集）来解释。

1. 位与运算 (&)：

   • 这是一个非常基础的逻辑运算。
   • 在 CPU 层面，它通常只需要一个时钟周期就能完成。
   • 它直接在处理器的算术逻辑单元（ALU）中执行，就像 ADD (加法)、XOR (异或) 一样，是硬件原生支持的最快操作之一。

2. 取模运算 (%)：

   • 取模运算的本质是除法。
   • 除法是 CPU 中最复杂的算术运算之一。它无法在一个时钟周期内完成。
   • 现代 CPU 虽然对除法做了很多优化，但它仍然需要一个迭代的过程（类似我们手算长除法），可能需要几十个甚至上百个时钟周期。
   • CPU 执行 a % n 时，实际执行的是一条 DIV (除法) 指令，然后从特定的寄存器中获取余数。这个 DIV 指令的执行时间远长于 AND 指令。

一个形象的比喻：

• & 运算：就像你有一排开关（二进制位），n-1 告诉你哪些开关需要保持原样，哪些需要直接关掉。你扫一眼，一次性操作就完成了。
• % 运算：就像你有一堆苹果 (hash)，要分给 n 个人，你想知道最后剩下几个。你需要一个一个地分（或者一组一组地分），这是一个重复性的、更费时的工作。

总结

HashMap 的设计者通过一个巧妙的约束——强制容量 n 必须是 2 的幂次方，成功地将一个在数学上很普遍但计算上很慢的操作（% 取模），转换成了一个在计算机中执行效率极高的操作（& 位与）。

这个优化虽然看起来微小，但 HashMap 的每一次 put, get, remove 操作都需要进行索引计算。将这个最高频的操作性能提升几十倍，对于整个 HashMap 的性能来说是至关重要的，也是其实现 O(1) 平均时间复杂度的基石之一。