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

大家好,我是一航!

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

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

代码语言:javascript
复制
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

解释了一圈儿,发现,没有示例的前提下,要把这个问题给说清楚,稍微还有点麻烦;索性就写篇文章,来聊聊这里面到底有些什么套路?

先说结论

一切的操作,只为增大随机性,减少hash的碰撞几率;让值保存的位置更加分散,散列性更好,提高读写性能。

本文将探讨以下几个问题?

  1. 为什么计算hash要做h ^ (h >>> 16)运算?
  2. 为什么槽位数(数组长度)必须是2^n
  3. HashMap能不能用空对象(null)作为key?

带着结论和问题,一起来分析一下;

准备工作

在分析之前,我们需要来回顾一下&(与运算)|(或运算)^(异或运算)以及位运算符,这几个是前提,不然后面就没办法进行了;

&(与运算)

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

示例:

代码语言:javascript
复制
  1101   (10进制:15)
& 1001   (10进制:11)
--------------------
= 1001   (10进制:11)

Java代码:

代码语言:javascript
复制
public static void main(String[] args) {
    System.out.println("15 & 11 = " + (15 & 11));
}

|(或运算)

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

示例:

代码语言:javascript
复制
  1101   (10进制:15)
| 1001   (10进制:11)
--------------------
= 1101   (10进制:15)

Java代码:

代码语言:javascript
复制
public static void main(String[] args) {
    System.out.println("15 | 11 = " + (15 | 11));
}

^(异或运算)

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

代码语言:javascript
复制
  1101   (10进制:15)
^ 1001   (10进制:11)
--------------------
= 0100   (10进制:4)

Java代码:

代码语言:javascript
复制
public static void main(String[] args) {
    System.out.println("15 ^ 11 = " + (15 ^ 11));
}
  • 位移运算符

有符号左移 << 向左移动x位(顶点在哪个方向就往哪个方向移动),无论正负数低位(最右边)都补x个0; 示例:20  << 2

代码语言:javascript
复制
20的二进制(反码,补码):0001 0100   
         向左移动两位后:0101 0000
                 结果:80

示例:-20<<2

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

  • 有符号右移 >> 向右移动x位,如果该数是正数,则高位(最左边)补x个0,如果是负数,则最高位补x个1 示例:20>>2

代码语言:javascript
复制
原码(反码,补码):00010100
右移两位(最左边两位添0)
原码(反码,补码):00000101
结果:5

示例:-20  >> 2

代码语言:javascript
复制
原码:10010100
反码:11101011    // 符号位不变,其他位取反
补码:11101100    // 反码 + 1
右移两位(最左边两位添1)
补码:11111011
反码:11111010    // 补码 - 1
原码:10000101    // 符号位不变,其他位取反
结果:-5
代码语言:javascript
复制
原码(反码,补码):00000000 00000000 00000000 00000010
右移一位(最左边一位添0)
原码(反码,补码):00000000 00000000 00000000 00000001
结果:1

示例:-2>>>1

代码语言:javascript
复制
原码: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
代码语言:javascript
复制
h = key.hashCode()
  • 第二步,计算HashMap的hash
代码语言:javascript
复制
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  • 第三步,计算槽位(数组下标)i = (n - 1) & hash]
代码语言:javascript
复制

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)

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

代码语言:javascript
复制
public static void main(String[] args) {
    Map map = new HashMap();
    map.put("hello world", "1");
}

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

槽位计算过程如下:

代码语言:javascript
复制
   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
复制
  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
复制
     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
复制
   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
复制
         hash  01101010 11101111 10001000 00101011
&
(17 - 1) = 16  00000000 00000000 00000000 00010000
----------------------------------------------
            =  00000000 00000000 00000000 00000000
  十进制 =  0

由于16的二进制是00010000,最终参与&(与运算)的只有1位,其他的值全部被0给屏蔽了;导致最终计算出来的槽位下标只会是016,那么所有的值也就只会保存在这两个槽位下;其他索引将永远无法命中,这对HashMap来说,无疑是灾难性的,保存的值越多,存取效率将会大大降低。

问题三:HashMap能不能用空对象(null)作为key?

答案是:可以的

从计算key hash值的源码就能看出:

代码语言:javascript
复制
static final int hash(Object key) {
    int h;
    return (key == null) ?  : (h = key.hashCode()) ^ (h >>> );
}

(key == null)时得到的hash值为0,带入到槽位计算公式(n - 1) & hash,空对象是保存的槽位是:0;

示例代码:

代码语言:javascript
复制
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
复制
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、槽位运算,大神也要将性能发挥到极致,可能这就是差别吧!