乐趣区

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

jiezi

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 & n 和 i = 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 开发手册（嵩山版）》最新公布，速速下载！

感觉不错，别忘了顺手点赞 + 转发哦！

退出移动版