hashMap高低位异或原理

2. 散列函数
   将整数散列最常用的方法就是除留余数法。为了均匀地散列键的散列值，通常都会把数组的大小取素数（HashTable 的初始大小就是 11），因为素数的因子少，余数相等的概率小，冲突的几率就小。

HashMap 的容量始终是 2 的次幂，这是一个合数，之所以这样设计，是为了将取模运算转为位运算，提高性能。这个等式h % length = h & (length-1)成立的原因如下：

2^1 = 10          2^1 -1 = 01 
2^2 = 100         2^2 -1 = 011 
2^3 = 1000        2^3 -1 = 0111
2^n = 1(n个零)     2^n -1 = 0(n个1) 

右边是 2^n 的二进制特点，左边是 2^n-1 的特点，可以发现当 length = 2^n 时，h & (length-1) 的结果正好位于 0 到 length-1 之间，就相当于取模运算。

转为位运算后，length-1 就相当于一个低位掩码，在按位与时，它会把原散列值的高位置0，这就导致散列值只在掩码的小范围内变化，显然增大了冲突几率。为了减少冲突，HashMap 在设计散列算法时，使用高低位异或，变相的让键的高位也参与了运算，代码如下：

static final int hash(Object key) { // JDK8
  int h;
  // h = key.hashCode()  1. 取hashCode值
  // h ^ (h >>> 16)      2. 高16位与低16位异或，变相保留高位的比特位
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// JDK7 的源码，JDK8 没有这个方法，但原理一样
static int indexFor(int h, int length) {
   return h & (length-1); // 3. 取模运算
}

高位的移位异或，既能保证有效的利用键的高低位信息，又能减少系统开销，这样设计是对速度、效率和质量之间的权衡。