为什么 HashMap 要用 h^(h ＞＞＞16) 计算hash值？槽位数必须是 2^n?

以下是Java8中HashMap计算key对应hash的源码：

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

主要是为了只为增大随机性，减少hash的碰撞几率；让值保存的位置更加分散，散列性更好，提高读写性能。

以String类型"test"为例，看看区别：

### （1）为什么需要左移16位

通过如下代码打印一下"test"的hashcode中32位的二进制
```java
    public static void print(int a){
        //输出32位二进制表示
        System.out.print(a+"的二进制表示:");
        for(int i=31;i>-1;i--)
            System.out.print((a&(1<<i))==0?0:1);
    }
```
输出

3556498的二进制表示:00000000001101100100010010010010

HashMap在计算槽位的时候，是通过 （长度 - 1）& hash(key)

(n - 1) & hash

由于HashMap在使用中一般都是数据量比较少，如果用默认的16位来取槽位

00000000001101100100010010010010&1111

打印

0010

最终在数组的位置下标为0010，通过上面观察发现，高16位，很难有机会参与运算，导致随机性降低

而将高16左移,得到00000000000000000000000000110110，使得高16位也能参与运算，增加了散列

00000000001101100100010010010010^00000000000000000000000000110110

## （2）为什么HashMap中计算hash用^（异或运算）而不是&(与运算)、|(或运算)

使用异或运算为0和1的概率都是50%

1^1 = 0
	1^0 = 1
	0^1 = 1
	0^0 = 0

使用与运算为0和1的概率分别为75%和25%，会导致结果偏向0多

1&1 = 1
	1&0 = 0
	0&1 = 0
	0&0 = 0

使用或运算为0和1的概率分别为25%和75%，会导致结果偏向1多

1|1 = 1
	1|0 = 1
	0|1 = 1
	0|0 = 0

由此可以看出，使用异或运算概率更平衡

### （3）为什么HashMap的数组大小必须是2的倍数

由于计算槽位（数组下标）的方式为(n - 1) & hash

如果允许使用非2的倍数计算，例如15，此时计算方式为：

1110&hash
	
由上可以看出，1的槽位永远无法放入数据，因为0&任意数都为0。导致槽位遗漏