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

2022-04-25 | 0 评论 | 0 浏览

如遇图片加载失败，可尝试使用手机流量访问

大家好，我是一航！

昨天中午，一位粉丝朋友在微信私信我，问：为啥HashMap的hash值计算格式是这样：(h = key.hashCode()) ^ (h >>> 16)？h ^ ^ (h >>> 16)是什么意思？

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

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

示例：

  1101   (10进制：15)
& 1001   (10进制：11)
--------------------
= 1001   (10进制：11)

Java代码：

public static void main(String[] args) {
    System.out.println("15 & 11 = " + (15 & 11));
}

如遇图片加载失败，可尝试使用手机流量访问

|(或运算)

两个二进制数值如果在同一位上至少有一个1，则结果中该位为1，否则为0

示例：

  1101   (10进制：15)
| 1001   (10进制：11)
--------------------
= 1101   (10进制：15)

Java代码：

public static void main(String[] args) {
    System.out.println("15 | 11 = " + (15 | 11));
}

如遇图片加载失败，可尝试使用手机流量访问

^(异或运算)

两个二进制数值如果在同一位上相同，则结果中该位为0，否则为1

  1101   (10进制：15)
^ 1001   (10进制：11)
--------------------
= 0100   (10进制：4)

Java代码：

public static void main(String[] args) {
    System.out.println("15 ^ 11 = " + (15 ^ 11));
}

如遇图片加载失败，可尝试使用手机流量访问

位移运算符

有符号左移 <<

向左移动x位（顶点在哪个方向就往哪个方向移动），无论正负数低位（最右边）都补x个0；

示例：20 << 2

20的二进制（反码，补码）：0001 0100 　　
         向左移动两位后：0101 0000
                 结果：80

示例：-20 << 2

原码：1001 0100
反码：1110 1011      // 符号位不变，其他位全部取反
补码：1110 1100      // 反码+1
左移两位后：1011 0000
反码：1010 1111      // 在右移动后的补上上-1
原码：1101 0000      // 除符号位外，反码其他位全部取反
结果：-80

有符号右移 >>

向右移动x位，如果该数是正数，则高位（最左边）补x个0，如果是负数，则最高位补x个1

示例：20>>2

原码（反码，补码）：00010100
右移两位（最左边两位添0）
原码（反码，补码）：00000101
结果：5

示例：-20 >> 2

原码：10010100
反码：11101011    // 符号位不变，其他位取反
补码：11101100    // 反码 + 1
右移两位（最左边两位添1）
补码：11111011
反码：11111010    // 补码 - 1
原码：10000101    // 符号位不变，其他位取反
结果：-5

无符号右移 >>>

和 >>类似，但不关注符号位，左侧全部补0；

示例：2>>>1

原码（反码，补码）：00000000 00000000 00000000 00000010
右移一位（最左边一位添0）
原码（反码，补码）：00000000 00000000 00000000 00000001
结果：1

示例：-2>>>1

原码：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  // 与反码相同
结果：2147483647

HashMap的hash、槽位计算

HashMap的底层数据结构是 数组+链表+红黑树，数组的槽位计算是整个存取的第一步；以下并非HashMap的详细过程，仅仅是与本文计算hash、数组槽位有关的步骤，其他与本文主题无关步骤，这里就不详细展开了

第一步，获取key的hash
```
h = key.hashCode()
```

第二步，计算HashMap的hash

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

第三步，计算槽位（数组下标）i = (n - 1) & hash]

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    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)`？

根据上面的步骤，我们用一个示例来演算一下

public static void main(String[] args) {
    Map map = new HashMap();
    map.put("hello world", "1");
}

实例化HashMap并没有指定长度，默认数组的长度 n = 2^4 = 16；

槽位计算过程如下：

   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()

对象的hashCode()是一个int值，取值范围为：[-2147483648,2147483647]

文本 hashCode() 二进制

"hello world" 1,794,106,052 01101010 11101111 11100010 11000100
h >>> 16

将hashCode无符号右移16位

操作值

hashCode() 1,794,106,052

二进制 01101010 11101111 11100010 11000100

h >>> 16 00000000 0000000001101010 11101111

文本	hashCode()	二进制
"hello world"	1,794,106,052	01101010 11101111 11100010 11000100

操作	值
hashCode()	1,794,106,052
二进制	01101010 11101111 11100010 11000100
h >>> 16	00000000 0000000001101010 11101111

hash = h ^ (h >>> 16)

操作说明：高16位不动；低16位与高16位做异或运算；高16位的参与，增加了结果的随机性

  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)
```
     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这个步骤，会是什么过程呢？槽位计算步骤就简单很多了

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**运算的时候，计算过程如下：

         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值的源码就能看出：

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

当 (key == null)时得到的hash值为0，带入到槽位计算公式 (n - 1) & hash，空对象是保存的槽位是：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已经被赋上值，从而导致最终值取不出来：

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、槽位运算，大神也要将性能发挥到极致，可能这就是差别吧！

🔥阿里云2核2G3M服务器，限时99元/年，续费同价，点击查看>🔥
🔥腾讯云双11，服务器1.8折，买一年送3个月>🔥

标题：为什么 HashMap 要用 h^(h >>>16) 计算hash值？槽位数必须是 2^n?
作者：码霸霸
地址：https://blog.lupf.cn/articles/2022/04/25/1650850273820.html

准备工作

HashMap的hash、槽位计算

问题一：为什么计算hash要做 h ^ (h >>> 16)？

假如没有做 h ^ (h >>> 16)运算

问题二：为什么槽位数（数组长度）必须是 2^n？

问题三：HashMap能不能用空对象（null）作为key？

问题一：为什么计算hash要做 `h ^ (h >>> 16)`？

假如没有做 `h ^ (h >>> 16)`运算

问题二：为什么槽位数（数组长度）必须是 `2^n`？