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

  |   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的碰撞几率;让值保存的位置更加分散,散列性更好,提高读写性能。

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

  1. 为什么计算hash要做 h ^ (h >>> 16)运算?
  2. 为什么槽位数(数组长度)必须是 2^n
  3. 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,05201101010 11101111 11100010 11000100
  • h >>> 16

    将hashCode无符号右移16位

    操作
    hashCode()1,794,106,052
    二进制01101010 11101111 11100010 11000100
    h >>> 1600000000 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给屏蔽了;导致最终计算出来的槽位下标只会是 016,那么所有的值也就只会保存在这两个槽位下;其他索引将永远无法命中,这对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、槽位运算,大神也要将性能发挥到极致,可能这就是差别吧!



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