前言

开门见山，HashMap这样做有两点原因

  1. 提升计算效率，更快算出元素的位置
  2. 减少哈希碰撞，使得元素分布均匀

提升计算效率

我们先看put方法的细节： 

public V put(K key, V value) { return putVal(hash(key), key, value, false, true);
    }

其中hash(key)如下： 

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

其中(h = key.hashCode()) ^ (h >>> 16)暂时不需要理解，会在文尾进行分析，这里只需要知道hash()方法返回二次运算后的哈希值即可。

接着回到putVal()方法中：

可以看到，对于一个key，拿到hash(key)后，之后要确定这个key在数组中的位置，我们一般倾向于对数组长度length取余，余数是几，就在数组的第几个位置上，简单方便。

但对于机器而言，位运算永远比取余运算快得多，在length为2的整数次方的情况下，hash(key)%length能被替换成高效的hash(key)&（length-1）,两者的结果是相等的。

减少哈希碰撞

如果数组长度是2的整数次方时，也就是一个偶数，length-1就是一个奇数，奇数的二进制最后一位是1，因此不管hash(key)是多少，hash(key)&(length-1)的二进制最后一位可能是0，也可能是1，取决于hash(key)。即如果hash(key)是奇数的话，则映射到数组上第奇数个位置上。

如果length是一个奇数的话，length-1就是一个偶数，偶数的二进制最后一位是0，则不管hash(key)是奇数还是偶数，该元素都会被映射到数组上第偶数个位置上，奇数位置上没有任何元素！

因此，数组长度是一个2的整数次方时，哈希碰撞的概率起码能下降一半，而且所有元素也能均匀地分布在数组上。

key.hashCode()^ (h >>> 16)

可能很多人都不知道这段代码的作用，下面我谈谈自己的想法。

首先需要理解>>>的含义，即无符号右移，高位补0。例如： 

0111 1110 0000 1111 1011 0001 0101 1010

右移16位得到

0000 0000 0000 0000 0111 1110 0000 1111

为什么要使用这个运算呢，直接返回key的哈希值不好吗？

一般来说，任意一个对象的哈希值比较大，随便实例化一个对象，得到它的hash值

转换成2进制后，得到 

0011 1001 1010 0000 0101 0100 1010 0101

而HashMap的长度一般就在[1，2^16]左右，取length=16为例，那么直接使用key的哈希值&(length-1)后，得到 

0011 1001 1010 0000 0101 0100 1010 0101
&
0000 0000 0000 0000 0000 0000 0000 1111
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101

可见，运算后的结果对哈希值的高位无效，即如果两个不同对象的哈希值仅仅在高位上不一样的话，依然会存在哈希冲突的情况。因此，我们现在打算让运算后的结果对哈希值的高位以及低位都有效。

而对哈希值再次运算后，即使用key.hashCode()^ (h >>> 16)运算后，将哈希值的低16位异或了高16位，让高位与低位都影响到了对之后位置的选择上。

那为什么使用^异或呢，使用|以及&不好吗？

^能保证两个数都能影响到最终的结果，而|中只要一个为1，不管对方是多少，结果都为1，&也是同样的道理，有0则0。

区别两个细微对象的不同，就要深挖其细微之处。因此要在最大程度上避免哈希冲突，就越要使用到所有已知的特征，不能认为细微就没用。