HashMap浅出

0. 背景

好久没动脑子去思考 hashmap 的设计了，这次做个简单分析。

1. hash 优化

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

原hash：1111 1111 1111 1111 1111 1010 0111 1100
右移16位：0000 0000 0000 0000 1111 1111 1111 1111
异或运算：1111 1111 1111 1111 0000 0101 1000 0011

在低16位中，让高低16位都参与进行了异或，尽量避免一些hash值后续出现冲突，大家可能会进入数组的同一个位置，增加链表长度。

2. 寻址优化

(n - 1) & hash，即 hash 对 n 取模结果一样。
高位没有参与与运算。

3. 扩容的寻址

数组长度为 16 时：
n-1：0000 0000 0000 0000 0000 0000 0000 1111
hash：1111 1111 1111 1111 0000 1111 0000 0101
&结果：0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）

n-1：0000 0000 0000 0000 0000 0000 0000 1111
hash：1111 1111 1111 1111 0000 1111 0001 0101
&结果：0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）

数组长度为 32 时：
n-1：0000 0000 0000 0000 0000 0000 0001 1111
hash：1111 1111 1111 1111 0000 1111 0000 0101
&结果：0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）

n-1：0000 0000 0000 0000 0000 0000 0001 1111
hash：1111 1111 1111 1111 0000 1111 0001 0101
&结果：0000 0000 0000 0000 0000 0000 0001 0101 = 21（index = 5+16的位置）

因此，只需要判断结果是否多了一个 bit 的 1，来决定新的 index 是不变，还是等于 index + oldCap