HashMap(jdk1.8)数组下标计算分析

前言

本章分析下HashMap在新增元素时为什么要选择这么计算数组下标。

计算数组下标

首先，复习下数组下标的定位逻辑：

// 计算key的hash值
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 计算数组下标 数组长度为2的倍数
(n - 1) & hash

总结其逻辑就是三步：

获取key的hashCode值 h，获取h的无符号位移16的结果
1中的结果做异或运算
2中重新计算hash值与数组长度n-1做与运算

为何要 h>>>16

HashMap中数组的初始长度是16，换成二进制的话就是

0000 0000 0000 0000 0000 0000 0001 0000

那么在执行 h & (n-1) 时候，如下：

0000 0000 0000 0000 0000 0000 0000 1111 （n-1）
0000 0000 1010 0101 1010 0101 1100 0110 （h）

会发现这里h只有低位参与了运算，结果会相对集中
所以，先将h无符号位移16位，这样可以让其高位参加运算，计算下标时会更随机

为何使用 ^ 计算hash

接下来看第二步，是将h的高低位做异或运算，这里为何选择异或呢？
先复习下位运算的知识：

a&b 先将a,b转化为二进制数，当且仅当相同位数都为1时，结果是1，否则为0
即 1&1 = 1； 0&1，1&0，0&0 = 0
a|b 先将a,b转化为二进制数，当且仅当相同位数都为0时，结果是0，否则为1
即 0|0 = 0； 0|1，1|0，1|1 = 1
a^b 先将a,b转化为二进制数，当且仅当相同位数只有一个为1时，结果是1，否则为0
即 1^1，0^0 = 0； 0&1，1&0 = 1

很容易看出，异或的计算结果相对更加平均，而重新计算hash的目的就是为了使结果更随机，
所以或运算和与运算都不太适合。

为何数组长度是2的N次方

一个数字是2的N次方，那么其二进制只有一位是1，其他位都是0.
而当其减去1后，比之前1所在低的位都会为0，以16为例

0000 0000 0000 0000 0000 0000 0001 0000 ->16
0000 0000 0000 0000 0000 0000 0000 1111 ->15

当15作为二进制参与运算时，会发现不论参与计算的hash值是多少，其结果范围被限制在低位
的四个1中，其效果与取模有异曲同工之妙。
但是位运算的优势在于其计算速度更快，所以HashMap的数组要保持2的N次方。

总结

在一番分析后，感觉对HashMap计算数组下标的逻辑有了清晰的理解。
也很佩服源码作者的智慧，设计得十分巧妙，且合理。