HashMap中的位运算

HashMap是基于哈希表实现的Map，其内部结构为数组+单链表/红黑树。

1、计算table位置

当要放入一个元素的时候，首先要解决的问题就是如何将这些元素平均地放置在数组中的各个位置，以减少哈希冲突。

假设数组table的长度为n（可放置的位置下标为：0,1,2,...,n-1；假设元素的Hash值都是理想的），首先想到的就是采用取余的方法：

hash % n

但是这种取余计算对计算机来说是相对比较慢的，解决思路就是使用位运算来替代取余。但是如果想要使用位运算进行取余操作，就有一个前提条件：取余操作中的被除数必须为2的倍数（Power of two），所以HashMap中的数组（Node<K,V>[] table）的length会一直保持为2的倍数（即2的m次幂）进行扩容（扩容机制：元素个数大于table.length * load_factor，默认值为16*0.75）。

此时，就可以使用位运算进行取余操作（位运算的效率远远高于%运算）：

(n - 1) & hash

2、计算key的哈希值

以上计算table位置的时候，我们假设键值对key的hash值都是均匀的，那么，怎么才能保证key的hash值尽量均匀，较少冲突呢？

计算key的哈希值时的计算方法(JDK1.8)：

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

简单分析一下为什么要采用这样的计算方式。

key.hashCode()调用的是key键值类型自带的哈希函数，返回int型散列值。理论上散列值是一个int型，如果直接拿散列值作为下标访问HashMap主数组的话，考虑到2进制32位带符号的int表值范围从-2147483648到2147483648，前后加起来大概40亿的映射空间。只要哈希函数映射得比较均匀松散，一般是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取余运算，得到的余数才能用来访问数组下标。

前面我们直到，table的长度length为2的m次幂，即永远为2的倍数。

length	二进制：高2位全部为0	length-1	二进制：高2位全部为0
16	00000000 00010000	15	00000000 00001111
32	00000000 00100000	31	00000000 00011111
64	00000000 01000000	63	00000000 00111111
128	00000000 10000000	127	00000000 01111111
256	00000001 00000000	255	00000000 11111111

而与运算（&）的规则为：如果相对应位都是1，则结果为1，否则为0。这时候问题就来了，就算散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。如果散列本身做得不好，分布上成等差数列的漏洞，恰好使最后几个低位呈现规律性重复，就会使碰撞非常严重。

HashMap中为了解决这个问题，采取了这样一种措施：混合原始哈希码的高位和低位，以此来使低位的随机性更好。

Java中int类型的数字占4个字节，也就是32位，h >>> 32这个操作即将原始哈希码向右移动16位，然后将其与原始哈希码进行异或运算（^），异或的规则为：如果相对应位值相同为0，不同为1。这样，混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。这种将高位与低位进行掺杂的操作，是扰动函数的一种。即对原始哈希值进行了1次扰动：高16位移动到低16位后与自身进行异或。

在JDK1.7中，计算方式如下，做了5次扰动：

static final int hash(int h) {
   h ^= key.hashCode(); 
   h ^= (h >>> 20) ^ (h >>> 12);
   return h ^ (h >>> 7) ^ (h >>> 4);
}

Java 8可能认为扰动做1次就够了，多次扰动可能边际效用也不大，且会带来效率的下降（多次异或运算）。

参考

二次方取余技术在HashMap的应用

JDK 源码中 HashMap 的 hash 方法原理是什么？

Java源码分析：HashMap 1.8 相对于1.7 到底更新了什么？