HashMap扩容后是否需要rehash？

在 **JDK 8** 中，**HashMap** 扩容后仍然**需要进行 rehash**（重新计算并分配哈希值），但与 JDK 8 之前的实现有了一些**优化**，这让人产生了误解，认为 JDK 8 取消了 rehash 的过程。实际上，JDK 8 只是优化了 rehash 的实现方式，使得 rehash 的过程更加高效，减少了计算开销。 让我们详细解释这个问题： ### 1. **HashMap 扩容后仍然需要 rehash** 扩容时，HashMap 会将容量翻倍，并需要将所有已经存储的键值对重新分配到新的更大容量的数组中。这是因为扩容后的数组大小发生了变化，原先的哈希值映射位置不再适合新数组的容量。因此，仍然需要进行 rehash 来确定每个键的新位置。 ### 2. **JDK 8 中的 rehash 优化** 在 JDK 8 之前，扩容后，每个键的哈希值都会重新计算并取模，得到它在新数组中的位置。这个过程涉及到每个键的哈希值重新计算，开销相对较大。 **JDK 8 的优化**在于利用了**哈希值的二进制特性**，从而避免了重新计算哈希值的复杂运算。具体优化点如下： #### 1. **哈希值与容量的关系** HashMap 扩容后，新的容量是原来的两倍，也就是说，扩容前容量是 `2^n`，扩容后容量是 `2^(n+1)`。在 JDK 8 中，扩容后的 rehash 过程中，不需要重新计算每个键的哈希值，而是通过观察**哈希值的最低有效位（Lowest Significant Bit, LSB）** 来决定键的重新分配。 - **扩容前**，哈希值通过 `hash & (oldCapacity - 1)` 得到元素的位置。 - **扩容后**，哈希值通过 `hash & (newCapacity - 1)` 得到新数组中的位置。 扩容后，`newCapacity` 是 `oldCapacity` 的两倍，意味着新的索引只会受到哈希值的**新增的最高位**（新增的最高位是 1 还是 0）的影响。 #### 2. **如何判断键的分布** 由于容量扩展为两倍，键的哈希值不会重新计算，只需要根据现有的哈希值，判断是否需要移动到新的桶位置。这是通过**哈希值的新增位**来决定的： - 如果哈希值的新增位为 `0`，键保持在原位置。 - 如果哈希值的新增位为 `1`，键被重新映射到新数组中的新的位置（索引为旧索引 + `oldCapacity`）。 #### 3. **举例说明** 假设 HashMap 当前容量为 16（即 `oldCapacity = 16`），当 HashMap 扩容到 32 时，假设某个键 `A` 的哈希值是 `10101100`，那么： - 扩容前：通过 `hash & (16 - 1)` 计算它的索引。也就是 `hash & 1111`，得到结果为 `1100`（即 12）。 - 扩容后：通过 `hash & (32 - 1)` 计算它的索引，即 `hash & 11111`，新增的第五位是 `1`，所以这个键 `A` 需要被移到 `oldCapacity + 12 = 28` 的位置。 因此，在 JDK 8 中，HashMap 扩容后不再需要重新计算每个键的哈希值，而是通过观察哈希值的**高一位**来决定键是否需要移动到新的索引位置。 ### 3. **为什么说 JDK 8 不需要 rehash？** 有人认为 JDK 8 “不需要 rehash”，实际上是因为： - **不需要重新计算哈希值**：JDK 8 的 rehash 过程不需要重新计算每个键的哈希值，而是直接利用哈希值的最低位来判断新索引。这减少了重新计算哈希值的开销。 - **索引位置的快速判断**：通过位运算（判断新增位是 0 还是 1）可以快速确定键是否需要移动到新的位置，避免了复杂的重新分配操作。 ### 4. **JDK 8 的 rehash 与 JDK 7 的区别** - **JDK 7**：扩容后会重新计算每个键的哈希值，通过 `hash % newCapacity` 来计算新索引位置，这个过程涉及重新计算哈希值并进行取模运算。 - **JDK 8**：扩容后不会重新计算哈希值，而是通过位运算来判断键是否需要重新分配索引，优化了 rehash 过程。 ### 总结 1. **HashMap 扩容后仍然需要 rehash**，因为扩容后的数组大小发生了变化，需要重新分配键的存储位置。 2. **JDK 8 中的 rehash 过程被优化**，不需要重新计算哈希值，而是通过判断哈希值的高一位来决定键的新位置。这种优化使得 rehash 的过程更高效，减少了重新计算哈希值的开销。 因此，虽然 JDK 8 在 rehash 的实现上做了优化，但它并没有完全取消 rehash 过程，只是让这个过程更高效。

在JDK 1.8之后的 `HashMap` 中，扩容后不需要重新计算每个键值对的 `hash` 值，即不需要进行传统意义上的 `rehash`。这是因为 `HashMap` 的 `hash` 值计算已经经过优化。 ### 具体原因如下： 在 `HashMap` 中，`hash` 值是根据 `key` 的 `hashCode()` 通过高 16 位与低 16 位进行异或计算得出的，然后通过 `(n - 1) & hash` 计算得到数组的下标 `index`，其中 `n` 是数组的长度。 #### 1. **扩容前：** - 初始长度为 `n`，下标计算方式为 `index = (n - 1) & hash`。 #### 2. **扩容后：** - 扩容后的长度变为 `2n`，下标计算方式变为 `index = (2n - 1) & hash`。 由于 `2n` 是原来的两倍且是 2 的幂次，因此 `(2n - 1) & hash` 的结果只会比原来的 `(n - 1) & hash` 多一个高位的判断。这个高位判断决定了原来的 `index` 是否需要加上 `n`（原数组长度）。换句话说，在扩容后，元素要么保持在原来的 `index` 上，要么移动到新的 `index + n` 位置上。 - 如果 `hash` 值的第 `n` 位为 `0`，那么扩容后 `index` 位置不变。 - 如果 `hash` 值的第 `n` 位为 `1`，那么扩容后 `index` 位置变为 `index + n`。 ### 总结： 这种机制使得扩容后无需重新计算 `hash` 值，只需根据原有 `index` 和 `n` 位上的差异，简单地将元素放在新数组中的适当位置，从而大大提高了扩容的效率。