HashMap扩容是怎样扩容的，为什么都是2的N次幂的大小？

在 Java 中，**HashMap** 的扩容机制是它实现高效查找的关键之一。每当 HashMap 需要扩容时，新的容量通常是**当前容量的两倍**，而且**总是 2 的 N 次幂**。下面我用通俗的方式详细解释一下 HashMap 的扩容过程，以及为什么选择 2 的 N 次幂作为大小。 ### 1. **为什么需要扩容？** HashMap 是通过键的哈希值找到存储位置的，当存入的元素越来越多时，如果不扩容，哈希冲突的几率就会增加，链表或红黑树会变长，从而影响性能。因此，**当 HashMap 中存储的元素超过一定数量（即超过“负载因子”阈值）时**，它就需要进行扩容。 默认的**负载因子**是 0.75，这意味着当 HashMap 中的元素数量超过当前容量的 75% 时，HashMap 就会进行扩容。扩容的过程是将容量增大为当前容量的两倍，并将原来所有的元素重新放入新的更大的数组中。 ### 2. **扩容的具体步骤** 当 HashMap 需要扩容时，过程如下： 1. **创建一个新数组**：HashMap 首先创建一个新的数组，大小是当前数组的两倍。这个新的数组会用来存放重新计算哈希值后的键值对。 2. **重新计算哈希值并迁移数据**：所有原来存放在旧数组中的元素会按照新的数组大小，重新计算哈希值并迁移到新的数组中。因为数组大小翻倍，键值对的存储位置可能会发生变化。 举个例子： - 假设当前 HashMap 的容量是 4，插入了 3 个元素：`A, B, C`。 - 当扩容到 8 时，这些元素的哈希值会重新被计算，并根据新的容量分配新的存储位置。 ### 3. **为什么容量总是 2 的 N 次幂？** HashMap 的容量选择 2 的 N 次幂的原因是为了**加快计算存储位置的速度**，具体是通过**位运算**来优化哈希值的处理。让我们逐步解释其中的原因： #### 1. **哈希值映射到数组索引** HashMap 是根据键的哈希值通过取模运算 (`hash % 数组长度`) 将哈希值映射到数组的一个索引位置上的。假设数组的长度是 16，取模运算将哈希值映射到 [0, 15] 的范围内，保证每个键都有一个对应的数组位置。 但取模运算的开销相对较大，Java 中使用了更高效的**按位与运算**来代替取模。当数组的大小是 2 的 N 次幂时，`hash % 数组长度` 可以简化为 `hash & (数组长度 - 1)`，因为 `2^n - 1` 的二进制表示是全 1 的形式。 例如： - 假设数组大小为 16（即 2^4），二进制为 `10000`，那么 `16 - 1 = 15` 的二进制是 `1111`。 - 现在如果我们有一个哈希值 `10101100`，只需做 `hash & 1111` 就可以快速得到它在数组中的位置，而不需要进行取模计算。 #### 2. **均匀分布哈希值** 使用 2 的 N 次幂的好处是可以让哈希值更均匀地分布在数组的各个槽位上。因为按位与运算能够保留哈希值的低位特征，而这些低位特征在经过良好的哈希函数处理后，通常是比较随机和均匀的。 如果数组长度不是 2 的幂次，例如是 10，那么 `hash % 10` 这样的取模运算会引入更多不规则的映射，哈希值分布可能不均匀，导致冲突增多，进而影响查找效率。 ### 4. **扩容为什么是容量的两倍？** 每次扩容时，容量都会增加为原来的两倍，这是为了保证： - **哈希值重新分配的效率**：扩容时，所有的键值对都要重新计算哈希值。如果容量是 2 的倍数，只需要根据新的大小简单地调整哈希值的低位即可，无需复杂的重新计算。 - **均匀分布**：扩容成 2 的倍数后，哈希值可以被更加均匀地分布在新的数组中，降低冲突概率，提高性能。 举个例子： - 假设某个键的哈希值是 `10101100`，初始数组长度为 16，取模结果是 `hash & 1111`，得到的结果是 `1100`，即索引 12。 - 扩容到 32 后，取模变为 `hash & 11111`，此时只需看哈希值的多一位即可。如果第 5 位是 `0`，键保持原位；如果是 `1`，键就会被移到新的索引。 ### 5. **通俗总结** - **扩容的原因**：当 HashMap 中存储的元素超过一定数量（负载因子）时，为了避免冲突和提高查找效率，需要将数组大小变为原来的两倍。 - **2 的 N 次幂的好处**：将数组大小设为 2 的幂次，可以利用位运算快速计算哈希值的存储位置，避免复杂的取模运算，提升效率。同时，它还能保证哈希值均匀分布在数组中，减少冲突。 - **扩容后的再哈希**：扩容后，所有的键值对都会重新计算哈希值，并按照新的数组大小重新分配位置。这一步保证了 HashMap 的效率和数据分布的均衡性。 通过这些机制，Java 中的 HashMap 能够在大多数情况下保持高效的查找和插入性能，尤其在数据量较大时。

### HashMap 的扩容机制及原因分析 #### 1. 触发扩容 在 `HashMap` 中，扩容是通过 `putVal()` 方法触发的。当添加一个新的键值对后，`HashMap` 会检查当前的元素个数是否超过了阈值（`threshold`），即 `数组长度 * 负载因子（0.75）`。如果超过阈值，则需要进行扩容。 #### 2. 扩容的步骤 扩容的具体步骤如下： **1. 计算扩容后的长度：** - 如果当前 `table` 为 `null`，则直接初始化一个长度为 16 的数组。 - 如果 `table` 的长度已经大于 `HashMap` 允许的最大值（2 的 30 次方），则不进行扩容，直接返回旧的 `table`。 - 其他情况下，将 `table` 的长度扩容为当前长度的两倍，然后计算新的扩容阀值（新数组长度 * 0.75）。 **2. 初始化新数组：** - 根据扩容后的数组长度初始化一个新的数组，并将其赋值给 `HashMap` 的成员变量 `table`。 - 此时，新数组 `newTab` 还是一个空数组，如果有其他线程并发访问 `HashMap`，则可能会因为查找不到键值对而返回 `null`，即便这些键值对在旧的 `table` 中存在。这也是 `HashMap` 线程不安全的表现之一。 **3. 迁移元素：** - 由于 `HashMap` 的数组长度总是 2 的幂次方，扩容后长度变为原来的两倍。因此，可以利用 `hash % length = hash & (length - 1)` 的性质，通过简单的计算确定元素在扩容后的新数组中的位置。 - 当扩容时，遍历旧数组中某个下标 `index` 下的链表或红黑树节点，计算每个节点的新位置： - 如果 `hash & length == 0`，则新数组下标与旧数组一致，即 `index`。 - 如果 `hash & length == 1`，则新数组下标为 `index + length`。 #### 3. 为什么 `HashMap` 的长度必须是 2 的幂次方？ `HashMap` 的长度总是设置为 2 的幂次方，主要原因有以下几点： 1. **提高效率：** - 通过 `hash % length` 计算数组下标的过程在 `HashMap` 中被优化为 `hash & (length - 1)`。当 `length` 是 2 的幂次方时，`length - 1` 是一个全为 1 的二进制数，与 `hash` 值进行按位与操作即可快速得到数组下标。这种位运算要比取模运算快得多。 2. **减少冲突：** - 当数组长度为 2 的幂次方时，`hash & (length - 1)` 能够使 `hash` 值的每一位都参与下标计算，从而有效减少哈希冲突，保证键值对在数组中的分布更为均匀。 3. **简化扩容迁移过程：** - 扩容后，只需要根据 `hash & length` 的结果来决定元素在新数组中的位置，不需要重新计算 `hash` 值，也无需重新分配大部分元素的位置。这大大简化了扩容过程，提高了性能。 #### 4. 迁移元素的详细过程 假设 `HashMap` 的初始数组长度为 `16`（即 `length = 16`），扩容后长度为 `32`。在扩容时，会按照以下规则对元素进行重新分配： - 对于链表中的每个元素，计算 `hash & (new length - 1)`，如果结果为 `0`，则元素位置不变；如果结果为 `1`，则元素移动到 `index + old length` 的位置。 这种方式通过简单的位运算，轻松将旧数组中的元素重新分配到新数组的两个位置（即原位置和 `原位置 + old length`），极大地优化了 `HashMap` 的扩容过程。 总结来说，`HashMap` 选择长度为 2 的幂次方并通过位运算进行扩容，能够有效提高计算效率，减少冲突，并且简化扩容时的元素迁移过程。