面试题 HashMap中key的存储索引是怎么计算的

1. 计算键的哈希值：
   HashMap使用键的hashCode()方法计算键的哈希值。为了减少哈希冲突并使哈希值分布更均匀，JDK 1.8对哈希值进行了一些额外处理，即通过一个位运算将高位的哈希值混合到低位。

   final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }
   

   在这段代码中，首先调用键的hashCode()方法获得哈希值h，然后将h的高16位与低16位进行异或运算。这样做的目的是为了减少哈希冲突，使哈希值更加均匀地分布。

2. 计算索引值：
   哈希值计算出来之后，接下来需要将哈希值映射到数组的索引位置。HashMap的底层存储是一个数组，称为桶（bucket）。索引值的计算公式是：

   (n - 1) & hash
   

   其中，n是数组的长度，hash是经过处理后的哈希值。&操作是按位与运算，它能确保计算出来的索引值在数组的范围内。

   假设数组的长度是2的幂（HashMap的容量总是2的幂），则n - 1的二进制表示将是全1，比如容量为16时，n - 1就是15（二进制表示为1111）。这种情况下，(n - 1) & hash的结果相当于取哈希值的低几位，这样可以确保索引值在0到n-1之间。

总结起来，JDK 1.8中HashMap计算键的索引值的步骤如下：

1. 计算键的哈希值，通过hashCode()方法获得。
2. 对哈希值进行额外处理，通过(h = key.hashCode()) ^ (h >>> 16)来混合高位和低位。
3. 计算数组索引值，通过(n - 1) & hash，确保索引值在数组范围内。

以下是一个具体的代码示例来说明这一过程：

public class HashMapIndexCalculation {
    public static void main(String[] args) {
        String key = "exampleKey";
        int hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        int arrayLength = 16; // 假设HashMap的初始容量是16
        int index = (arrayLength - 1) & hash;
        System.out.println("Hash值: " + hash);
        System.out.println("索引值: " + index);
    }
}

通过上述步骤和代码，我们可以看到HashMap在JDK 1.8中是如何计算键的索引值的。