HashMap 中 key 的存储索引是怎么计算的？

### HashMap 中 key 的存储索引计算原理 在 `HashMap` 中，key 的存储索引主要分为以下几个步骤： #### 1. **计算 `hashCode`** 首先，根据 `key` 的 `hashCode()` 方法获取键的哈希值。`hashCode` 是每个对象的默认方法，用于返回对象的哈希值。理论上，这个哈希值应该尽量分布均匀，从而减少哈希冲突。 #### 2. **优化哈希值** 接着，`HashMap` 通过 `hash()` 方法进一步优化哈希值。在 JDK 8 中，这个方法的实现如下： ```java static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } ``` - **步骤**： - 先获取 key 的 `hashCode()` 值 `h`。 - 然后将 `h` 的高 16 位与低 16 位做异或操作 `(h ^ (h >>> 16))`，以此混合哈希值的高位和低位，增强了哈希值的随机性，减少哈希冲突。 - 这样做的好处是，即使 `hashCode()` 方法本身分布不均匀，优化后的哈希值能够更加均匀地映射到哈希桶中。 #### 3. **计算数组索引** 在计算出哈希值后，需要确定该键值对在 `HashMap` 中的具体存储位置。这一步通过对数组的长度取模来计算： ```java i = (n - 1) & hash; ``` - 其中 `n` 是数组的长度，`hash` 是经过优化后的哈希值，`&` 是按位与操作。 - `HashMap` 中，数组的长度 `n` 总是 2 的幂次方，因此 `(n - 1)` 的二进制形式就是全 1，比如 16 的二进制是 `10000`，而 15 的二进制是 `1111`。使用按位与操作 `&` 可以快速计算出 `hash` 值对应的索引。 #### 4. **为什么使用 `&` 而不是 `%`** - 通常情况下，我们使用 `%` 运算符来计算取模，但 `HashMap` 中使用 `&` 运算符来替代 `%`。这是因为 `%` 运算符的性能较低，而 `&` 在数组长度为 2 的幂时能更高效地计算索引。 - 例如，`a % b` 在 `b` 为 2 的幂时等价于 `a & (b - 1)`。因此，当数组长度是 2 的幂时，`(n - 1) & hash` 可以快速得到索引值。 #### 5. **示例** 假设某哈希值为 `10100101 11000100 00100101`，`HashMap` 的初始数组长度为 16（二进制 `10000`），此时 `(16 - 1) = 15`，二进制为 `1111`。 - 通过按位与操作： ``` 10100101 11000100 00100101 & 00000000 00000000 00001111 ------------------------- 00000000 00000000 00000101 ``` - 结果为 `00000101`，也就是十进制的 5，这表示该键值对应该存储在数组的第 5 个位置。 #### 6. **hash 方法的作用** `hash()` 方法的作用在于增强哈希值的随机性，通过将哈希值的高 16 位与低 16 位混合，减少了哈希冲突的发生，使得 `HashMap` 中的键值对更加均匀地分布在数组中。 #### 7. **总结** - `hashCode()` 方法获取键的哈希值。 - `hash()` 方法对哈希值进行优化，通过异或操作混合高低位，增加随机性。 - 通过 `(n - 1) & hash` 来计算存储的数组索引，以确定键值对在 `HashMap` 中的位置。 这样做确保了 `HashMap` 中键的分布尽可能均匀，减少冲突，优化性能。