为什么 HashMap 要用 h^(h >>>16) 计算hash值？槽位数必须是 2^n?
大家好，我是一航！
昨天中午，一位粉丝朋友在微信私信我，问：为啥HashMap的hash值计算格式是这样：(h = key.hashCode()) ^ (h >>> 16)？h ^ ^ (h >>> 16)是什么意思？
以下是Java8中HashMap计算key对应hash的源码：
代码语言：javascript代码运行次数：0运行复制static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
解释了一圈儿，发现，没有示例的前提下，要把这个问题给说清楚，稍微还有点麻烦；索性就写篇文章，来聊聊这里面到底有些什么套路？
先说结论：
一切的操作，只为增大随机性，减少hash的碰撞几率；让值保存的位置更加分散，散列性更好，提高读写性能。
本文将探讨以下几个问题？
为什么计算hash要做h ^ (h >>> 16)运算？为什么槽位数（数组长度）必须是2^n？HashMap能不能用空对象（null）作为key？带着结论和问题，一起来分析一下；
准备工作在分析之前，我们需要来回顾一下&(与运算)、|(或运算)、^(异或运算)以及位运算符，这几个是前提，不然后面就没办法进行了；
&(与运算)
两个二进制数值如果在同一位上都是1，则结果中该位为1，否则为0
示例：
代码语言：javascript代码运行次数：0运行复制 1101 (10进制：15)
& 1001 (10进制：11)
--------------------
= 1001 (10进制：11)
Java代码：
代码语言：javascript代码运行次数：0运行复制public static void main(String[] args) {
System.out.println("15 & 11 = " + (15 & 11));
}
|(或运算)
两个二进制数值如果在同一位上至少有一个1，则结果中该位为1，否则为0
示例：
代码语言：javascript代码运行次数：0运行复制 1101 (10进制：15)
| 1001 (10进制：11)
--------------------
= 1101 (10进制：15)
Java代码：
代码语言：javascript代码运行次数：0运行复制public static void main(String[] args) {
System.out.println("15 | 11 = " + (15 | 11));
}
^(异或运算)
两个二进制数值如果在同一位上相同，则结果中该位为0，否则为1
代码语言：javascript代码运行次数：0运行复制 1101 (10进制：15)
^ 1001 (10进制：11)
--------------------
= 0100 (10进制：4)
Java代码：
代码语言：javascript代码运行次数：0运行复制public static void main(String[] args) {
System.out.println("15 ^ 11 = " + (15 ^ 11));
}
位移运算符有符号左移 <<
向左移动x位（顶点在哪个方向就往哪个方向移动），无论正负数低位（最右边）都补x个0；
示例：20 << 2
代码语言：javascript代码运行次数：0运行复制20的二进制（反码，补码）：0001 0100
向左移动两位后：0101 0000
结果：80 示例：-20<<2
代码语言：javascript代码运行次数：0运行复制原码：1001 0100
反码：1110 1011 // 符号位不变，其他位全部取反
补码：1110 1100 // 反码+1
左移两位后：1011 0000
反码：1010 1111 // 在右移动后的补上上-1
原码：1101 0000 // 除符号位外，反码其他位全部取反
结果：-80
有符号右移 >>
向右移动x位，如果该数是正数，则高位（最左边）补x个0，如果是负数，则最高位补x个1
示例：20>>2
代码语言：javascript代码运行次数：0运行复制原码（反码，补码）：00010100
右移两位（最左边两位添0）
原码（反码，补码）：00000101
结果：5示例：-20 >> 2
代码语言：javascript代码运行次数：0运行复制原码：10010100
反码：11101011 // 符号位不变，其他位取反
补码：11101100 // 反码 + 1
右移两位（最左边两位添1）
补码：11111011
反码：11111010 // 补码 - 1
原码：10000101 // 符号位不变，其他位取反
结果：-5代码语言：javascript代码运行次数：0运行复制原码（反码，补码）：00000000 00000000 00000000 00000010
右移一位（最左边一位添0）
原码（反码，补码）：00000000 00000000 00000000 00000001
结果：1示例：-2>>>1
代码语言：javascript代码运行次数：0运行复制原码：10000000 00000000 00000000 00000010
反码：11111111 11111111 11111111 11111101 // 符号位不变，其他位取反
补码：11111111 11111111 11111111 11111110 // 反码 + 1
右移1位（无符号位运算符，最左边一位只添0）
补码：01111111 11111111 11111111 11111111
反码：01111111 11111111 11111111 11111111 // 高位为0，正数
原码：01111111 11111111 11111111 11111111 // 与反码相同
结果：2147483647HashMap的hash、槽位计算
HashMap的底层数据结构是数组+链表+红黑树，数组的槽位计算是整个存取的第一步；以下并非HashMap的详细过程，仅仅是与本文计算hash、数组槽位有关的步骤，其他与本文主题无关步骤，这里就不详细展开了
第一步，获取key的hash代码语言：javascript代码运行次数：0运行复制h = key.hashCode()第二步，计算HashMap的hash代码语言：javascript代码运行次数：0运行复制static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}第三步，计算槽位（数组下标）i = (n - 1) & hash]代码语言：javascript代码运行次数：0运行复制
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
....
}后续步骤，保存
略问题一：为什么计算hash要做h ^ (h >>> 16)？根据上面的步骤，我们用一个示例来演算一下
代码语言：javascript代码运行次数：0运行复制public static void main(String[] args) {
Map map = new HashMap();
map.put("hello world", "1");
}
实例化HashMap并没有指定长度，默认数组的长度n = 2^4 = 16 ；
槽位计算过程如下：
代码语言：javascript代码运行次数：0运行复制 h = key.hashCode() 01101010 11101111 11100010 11000100
h >>> 16 00000000 00000000 01101010 11101111
------------------------------------------------------------
hash = h ^ (h >>> 16) 01101010 11101111 10001000 00101011
(n - 1) = (2^4 - 1) 00000000 00000000 00000000 00001111
------------------------------------------------------------
(2^4 - 1) & hash 00000000 00000000 00000000 00001011
10进制结果 11过程分析:
h = key.hashCode()h >>> 16
将hashCode无符号右移16位hash = h ^ (h >>> 16)
操作说明：高16位不动；低16位与高16位做异或运算；高16位的参与，增加了结果的随机性代码语言：javascript代码运行次数：0运行复制 01101010 11101111 11100010 11000100
^ 00000000 00000000 01101010 11101111
-------------------------------------
= 01101010 11101111 10001000 00101011
(n - 1) & hash
n代码HashMap中数组的长度，初始的时候没有指定，默认情况下n就是2^4 = 16
(n - 1) = 16 - 1 = 15
那还有一个问题：为什么要n-1?
以默认长度：16（2^4） 为例，那数组对应的下标就是0-15之间
计算方式：hash % (2^4)；本质就是和长度取余
等价计算方式：hash & (2^4 - 1)代码语言：javascript代码运行次数：0运行复制 hash 01101010 11101111 10001000 00101011
&
(2^4 - 1) 00000000 00000000 00000000 00001111
----------------------------------------------
= 00000000 00000000 00000000 00001011
十进制 = 11由此，可以得出"hello world"最终所属的槽位就是：11
假如没有做h ^ (h >>> 16)运算前面已经明白了整个hash、槽位的计算过程，那如果没有h ^ (h >>> 16这个步骤，会是什么过程呢？槽位计算步骤就简单很多了
代码语言：javascript代码运行次数：0运行复制 hash = key.hashCode() 01101010 11101111 11100010 11000100
(n - 1) 00000000 00000000 00000000 00001111
------------------------------------------------------------
(n - 1) & hash = 00000000 00000000 00000000 00000100
结合以上示例会发现，整个hash值，除了低四位参与了计算，其他全部没有起到任何的作用，这样就会导致，key的hash值是低位相同，高位不同的话，计算出来的槽位下标都是同一个，大大增加了碰撞的几率；
但如果使用h ^ (h >>> 16)，将高位参与到低位的运算，整个随机性就大大增加了；
问题二：为什么槽位数（数组长度）必须是2^n？根据源码可知，无论是初始化，还是保存过程中的扩容，槽位数的长度始终是2^n；通过(2^n - 1) & hash公式计算出来的槽位索引更具散列性；假如默认槽位数n的长度不是16（2^4）,而是17，会出现什么效果呢？
在做**(n - 1) & hash**运算的时候，计算过程如下：
代码语言：javascript代码运行次数：0运行复制 hash 01101010 11101111 10001000 00101011
&
(17 - 1) = 16 00000000 00000000 00000000 00010000
----------------------------------------------
= 00000000 00000000 00000000 00000000
十进制 = 0由于16的二进制是00010000,最终参与&(与运算)的只有1位，其他的值全部被0给屏蔽了；导致最终计算出来的槽位下标只会是0或16，那么所有的值也就只会保存在这两个槽位下；其他索引将永远无法命中，这对HashMap来说，无疑是灾难性的，保存的值越多，存取效率将会大大降低。
问题三：HashMap能不能用空对象（null）作为key？答案是：可以的；
从计算key hash值的源码就能看出：
代码语言：javascript代码运行次数：0运行复制static final int hash(Object key) {
int h;
return (key == null) ? : (h = key.hashCode()) ^ (h >>> );
}
当(key == null)时得到的hash值为0，带入到槽位计算公式(n - 1) & hash，空对象是保存的槽位是：0；
示例代码：
代码语言：javascript代码运行次数：0运行复制public static void main(String[] args) {
Map map = new HashMap();
map.put(null, "1");
System.out.println(map.get(null));
}
能正常的取到值，但小心有坑：
既然这里能以null对象作为key，那么在保存值和取值的时候，务必要注意，很可能在存值的时候，key的对象还是null，但到取值的时候，key已经被赋上值，从而导致最终值取不出来：
代码语言：javascript代码运行次数：0运行复制public static void main(String[] args) {
HashMap map = new HashMap();
String key = null;
map.put(key, "1");
// .. 其他操作
key = "k";
System.out.println("用k取值：" + map.get(key));
System.out.println("用null取值：" + map.get(null));
}
这样，这个hash、槽位的计算”套路“算是说清楚了；
新手写代码，能跑就行，对于大神来说，写好才行；好的代码，都是从各个微小的细节入手，最终达到一个更加完美的效果；就单单一个hash、槽位运算，大神也要将性能发挥到极致，可能这就是差别吧！
友情链接