为什么 hash 值要与length-1相与？

在 `HashMap` 中，计算数组索引时采用 `hash & (length - 1)`，而不是使用传统的取模运算 `hash % length`。原因主要有以下几点： ### 1. **位运算的高效性** - **取模运算 `%`** 通常比位运算 `&` 要慢，尤其在数组长度是 2 的幂次方时，位运算可以更高效地完成同样的工作。 - **位运算 `&`** 的计算速度极快，因为它直接对二进制位进行操作，CPU 对这种操作的支持极好。在长度是 2 的幂时，`h & (length - 1)` 的效果等同于 `h % length`，但性能更优。 ### 2. **数组长度为 2 的幂次方** - 在 `HashMap` 中，数组的长度 `length` 总是 2 的幂次方（如 16、32 等），这意味着 `length - 1` 的二进制形式是一个低位全为 1 的数。例如，16 的二进制是 `10000`，而 15 的二进制是 `1111`。 - 通过 `hash & (length - 1)`，可以保留哈希值的低位部分，并且计算出的值始终落在 `[0, length-1]` 的范围内，即满足了数组索引的需求。 ### 3. **与取模运算的等价性** - 对于长度为 2 的幂次方的数组，`hash % length` 和 `hash & (length - 1)` 计算结果是相同的。二者的作用都是将哈希值映射到数组的索引范围内，但位运算的效率比取模运算高。 - 具体来说，当 `length` 是 2 的幂次方时，`h % length` 的结果等价于 `h & (length - 1)`，因为这种位运算可以快速取出哈希值的低位部分。 ### 4. **减少冲突的均匀性** - 使用 `&` 操作时，数组的长度是 2 的幂次方，通过这种操作确保了哈希值的均匀分布。由于 `length - 1` 的二进制形式是低位全 1，可以使哈希值的低位部分均匀映射到数组中，减少哈希冲突的发生。 ### 总结 `HashMap` 中使用 `hash & (length - 1)` 代替 `hash % length` 的主要原因是 **位运算比取模运算快得多**，尤其是在 `length` 是 2 的幂次方时，二者是等价的。通过这种方式，`HashMap` 提高了计算索引的效率，同时确保了哈希值的均匀分布，减少了冲突的概率。

在 `HashMap` 中，数组的长度总是 2 的幂次方，这样的设计有助于提高哈希表的性能和空间利用率，具体原因如下： ### 1. **提高哈希计算效率** - 当 `HashMap` 的数组长度是 2 的幂次方时，使用 `hash & (length - 1)` 进行索引计算可以快速取模。由于 `(length - 1)` 在二进制表示中全为 1，这使得位运算非常高效，同时可以确保哈希值的低位部分均匀分布在数组的各个位置。 - 例如，若 `length` 是 16（二进制为 `10000`），那么 `length - 1` 为 `15`（二进制为 `1111`）。通过 `&` 运算符与哈希值进行位运算，可以快速计算出数组索引，避免了 `%` 运算带来的性能损耗。 ### 2. **减少哈希冲突** - 当 `length` 是 2 的幂次方时，哈希值经过 `& (length - 1)` 操作后，能够更均匀地分布到哈希表的每一个槽位，降低了哈希冲突的几率。 - 假如 `length` 不是 2 的幂次方，比如 `length = 15`（二进制为 `1110`），那么 `hash & 14` 可能会导致一些哈希值无法被均匀分布到数组的每个位置，这样就容易产生哈希冲突，某些位置可能会有更多的元素，形成链表，影响查询效率。 ### 3. **避免空间浪费** - 如果数组长度不是 2 的幂次方，某些哈希值在经过 `& (length - 1)` 后可能会集中到某些特定的位置，从而导致其他位置被浪费。例如，当 `length = 15` 时（`1110`），最后一位始终为 0，导致奇数位的哈希值永远无法映射到有效的索引，造成空间浪费。 - 而当 `length` 是 2 的幂次方时，哈希值的每一位都能被充分利用，使得所有数组位置都能存储数据，从而避免了空间浪费。 ### 4. **自动将传入的容量调整为 2 的幂次方** - `HashMap` 提供的构造函数允许用户传入任意的容量，但为了保持性能和效率，`HashMap` 会自动将传入的容量调整为最近的 2 的幂次方。这是通过 `tableSizeFor(int cap)` 方法实现的： ```java static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } ``` - 这个方法的目的是找到大于或等于输入值 `cap` 的最近的 2 的幂次方。例如： - `tableSizeFor(10)` 会返回 16（2 的 4 次幂）。 - `tableSizeFor(20)` 会返回 32（2 的 5 次幂）。 - 通过这种机制，`HashMap` 保证了其内部数组的长度总是 2 的幂次方，这有助于提高哈希表的性能。 ### 5. **扩容的高效性** - 当 `HashMap` 需要扩容时，新数组的长度也是 2 的幂次方。这不仅保证了哈希计算的高效性，还使得在扩容过程中，原有元素可以更均匀地重新分布到新的数组中，减少了扩容带来的性能损耗。 ### 总结 `HashMap` 选择数组长度为 2 的幂次方，是为了在哈希计算时使用高效的位运算，同时保证哈希值能够均匀分布，减少冲突和空间浪费。此外，`HashMap` 会自动将用户指定的容量调整为最近的 2 的幂次方，从而确保性能和空间利用的最优。