乐趣区

关于java:美团一面JDK-18-中的-HashMap-如何应对-hash-冲突我懵逼了

1 什么是 hash 抵触

咱们晓得 HashMap 底层是由数组 + 链表 / 红黑树形成的,当咱们通过 put(key, value) 向 hashmap 中增加元素时,须要通过散列函数确定元素到底应该搁置在数组中的哪个地位,当不同的元素被搁置在了数据的同一个地位时,后放入的元素会以链表的模式,插在前一个元素的尾部,这个时候咱们称产生了 hash 抵触。

2 如何解决 hash 抵触

事实上,想让 hash 抵触齐全不产生,是不太可能的,咱们能做的只是尽可能的升高 hash 抵触产生的概率:上面介绍在 HashMap 中是如何应答 hash 抵触的?

当咱们向 hashmap 中 put 元素 (key, value) 时, 最终会执行 putVal() 办法,而在 putVal() 办法中,又执行了 hash(key) 这个操作,并将执行后果作为参数传递给了 putVal 办法。那么咱们先来看 hash(key) 办法干了什么。

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
    int h;
   // 判断 key 是否为 null, 如果为 null, 则间接返回 0;
   // 如果不为 null,则返回 (h = key.hashCode()) ^ (h >>> 16) 的执行后果
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

(h = key.hashCode()) ^ (h >>> 16)执行了三步操作:咱们一步一步来剖析:

第 1 步:h = key.hashCode()

这一步会依据 key 值计算出一个 int 类型的 h 值也就是 hashcode 值,例如

"helloWorld".hashCode() --> -1554135584
"123456".hashCode() --> 1450575459
"我爱 java".hashCode() --> -1588929438

至于 hashCode() 是如何依据 key 计算出 hashcode 值的,要分几种状况进行剖析:

  1. 如果咱们应用的本人创立的对象,在咱们没有重写 hashCode()办法的状况下, 会调用 Object 类的 hashCode()办法,而此时返回就是对象的内存地址值,所以如果对象不同,那么通过 hashcode()计算出的 hashcode 就是不同的。
  2. 如果是应用 java 中定义的援用类型例如 String,Integer 等作为 key,这些类个别都会重写 hashCode()办法,有趣味能够翻看一下对应的源码。简略来说,Integer 类的 hashCode()返回的就是 Integer 值, 而 String 类型的 hashCode()办法稍稍简单一点,这里不做开展。总的来说,hashCode()办法的作用就是要依据不同的 key 失去不同的 hashCode 值。

JDK 8 系列教程:

https://www.javastack.cn/cate…

第 2 步:h >>> 16

这一步将第 1 步计算出的 h 值无符号右移 16 位。

为什么要右移 16 位,当然是位了第三步的操作。

第 3 步:h ^ (h >>> 16)

将 hashcode 值的高下 16 位进行异或操作 (同 0 得 0、同 1 得 0、不同得 1) 失去 hash 值,举例说明:

  • 假如 h 值为:1290846991
  • 它的二进制数为:01001100 11110000 11000011 00001111
  • 右移十六位之后:00000000 00000000 01001100 11110000
  • 进行异或操作后:01001100 11110000 10001100 11110000
  • 最终失去的 hash 值:1290833136

那么问题来了: 明明通过第一步失去的 hashcode 值就能够作为 hash 返回,为什么还要要进行第二步和第三步的操作呢?答案是为了缩小 hash 抵触!

元素在数组中寄存的地位是由上面这行代码决定的:

// 将 (数组的长度 -1) 和 hash 值进行按位与操作:
i = (n - 1) & hash  // i 为数组对应地位的索引  n 为以后数组的大小

咱们将下面这步操作作为第 4 步操作,来比照一下执行 1、2、3、4 四个步骤和只执行第 1、4 两个步骤所产生的不同成果。

咱们向 hashmap 中 put 两个元素node1(key1, value1)node2(key2, value2),hashmap 的数组长度n=16

执行 1、2、3、4 四个步骤:

1.h = key.hashCode()

  • 假如计算的后果为:h = 3654061296
  • 对应的二进制数为:    01101100 11100110 10001100 11110000

2.h >>> 16

  • h 无符号右移 16 位失去:00000000 00000000 01101100 11100110

3.hash = h ^ (h >>> 16)

  • 异或操作后失去 hash:01101100 11110000 11100000 00000110

4.i = (n-1) & hash

  • n-1=15 对应二进制数 :    00000000 00000000 00000000 00001111
  • hash :   01101100 11110000 11100000 00000110
  • hash & 15 :    00000000 00000000 00000000 00000110
  • 转化为 10 进制:&ensp 5

最终失去 i 的值为 5,也就是说 node1 寄存在数组索引为 5 的地位。

同理咱们对(key2, value2) 进行上述同样的操作过程:

1.h = key.hashCode()

  • 假如计算的后果为:h = 3652881648
  • 对应的二进制数为:    01101100 11011101 10001100 11110000

2.h >>> 16

  • h 无符号右移 16 位失去:00000000 00000000 01101100 11011101

3.hash = h ^ (h >>> 16)

  • 异或操作后失去 hash:01101100 11110000 11100000 00101101

4.i = (n-1) & hash

  • n-1=15 对应二进制数 :    00000000 00000000 00000000 00001111
  • hash :   01101100 11110000 11100000 00101101
  • hash & 15 :   00000000 00000000 00000000 00001101
  • 转化为 10 进制:&ensp 13

最终失去 i 的值为 13,也就是说 node2 寄存在数组索引为 13 的地位

node1 和 node2 存储的地位如下图所示:

执行 1、4 两个步骤:

1.h = key.hashCode()

  • 计算的后果同样为:h = 3654061296
  • 对应的二进制数为:    01101100 11100110 10001100 11110000

4.i = (n-1) & hash

  • n-1=15 对应二进制数 :    00000000 00000000 00000000 00001111
  • hash(h) :   01101100 11100110 10001100 11110000
  • hash & 15 :   00000000 00000000 00000000 00000000
  • 转化为 10 进制:0

最终失去 i 的值为 0,也就是说 node1 寄存在数组索引为 0 的地位

同理咱们对(key2, value2) 进行上述同样的操作过程:

1.h = key.hashCode()

  • 计算的后果同样为:h = 3652881648
  • 对应的二进制数为:    01101100 11011101 10001100 11110000

4.i = (n-1) & hash

  • n-1=15 对应二进制数 :    00000000 00000000 00000000 00001111
  • hash(h) :   01101100 11110000 11100000 11110000
  • hash & 15 :   00000000 00000000 00000000 00000000
  • 转化为 10 进制:0

最终失去 i 的值为 0,也就是说 node2 同样寄存在数组索引为 0 的地位

node1 和 node2 存储的地位如下图所示:

置信大家曾经看出区别了:

当数组长度 n 较小时,n- 1 的二进制数高 16 位全副位 0,这个时候如果间接和 h 值进行 &(按位与)操作,那么只能利用到 h 值的低 16 位数据,这个时候会大大增加 hash 抵触产生的可能性,因为不同的 h 值转化为 2 进制后低 16 位是有可能雷同的,如下面所举例子中:key1.hashCode()key2.hashCode() 失去的 h 值不同,一个h1 = 3654061296,另一个h2 = 3652881648,然而可怜的是这 h1、h2 两个数转化为 2 进制后低 16 位是完全相同的,所以h1 & (n-1)h2 & (n-1) 会计算出雷同的后果,这也导致了 node1 和 node2 存储在了数组索引雷同的地位,产生了 hash 抵触。

当咱们应用进行 h ^ (h >>> 16) 操作时,会将 h 的高 16 位数据和低 16 位数据进行异或操作,最终得出的 hash 值的高 16 位保留了 h 值的高 16 位数据,而 hash 值的低 16 数据则是 h 值的高下 16 位数据独特作用的后果。所以即便 h1 和 h2 的低 16 位雷同,最终计算出的 hash 值低 16 位也大概率是不同的,升高了 hash 抵触产生的概率。

ps:这外面还有一个值的留神的点: 为什么是(n-1)?

咱们晓得 n 是 hashmap 中数组的长度, 那么为要进行 n - 1 的操作?答案同样是为了升高 hash 抵触产生的概率!

要了解这一点,咱们首先要晓得 HashMap 规定了数组的长度 n 必须为 2 的整数次幂,至于为什么是 2 的整数次幂,会在 HashMap 的扩容办法 resize() 里具体讲。

既然 n 为 2 的整数次幂,那么 n 肯定是一个偶数。那么咱们来比拟 i = hash & ni = hash & (n-1)有什么异同。

n 为偶数,那么 n 转化为 2 进制后最低位肯定为 0,与 hash 进行按位与操作后最低位仍肯定为 0,这就导致 i 值只能为偶数,这样就节约了数组中索引为奇数的空间,同时也减少了 hash 抵触产生的概率。

所以咱们要执行 n -1, 失去一个奇数,这样 n - 1 转化为二进制后低位肯定为 1,与 hash 进行按位与操作后最低位即可能位 0 也可能位 1,这就是使得 i 值即可能为偶数,也可能为奇数,充分利用了数组的空间,升高 hash 抵触产生的概率。

至此, JDK1.8 中 HashMap 是如何在存储元素时缩小 hash 产生就解说结束了!

起源:blog.csdn.net/weixin_43689776/article/details/99999126

近期热文举荐:

1.1,000+ 道 Java 面试题及答案整顿(2022 最新版)

2. 劲爆!Java 协程要来了。。。

3.Spring Boot 2.x 教程,太全了!

4. 别再写满屏的爆爆爆炸类了,试试装璜器模式,这才是优雅的形式!!

5.《Java 开发手册(嵩山版)》最新公布,速速下载!

感觉不错,别忘了顺手点赞 + 转发哦!

退出移动版