JDK1.8 中 HashMap 如何应对 hash 冲突?

沙海
沙海
沙海
2424
文章
2
评论
2021年11月23日04:54:45
评论
1 4701字阅读15分40秒
摘要

智能摘要

智能摘要

JDK1.8中HashMap是如何在存储元素时减少hash发生就讲解完毕了!最近面试BATJ,整理一份面试资料《Java面试BAT通关手册》,覆盖了Java核心技术、JVM、Java并发、SSM、微服务、数据库、数据结构等等。

原文约 3500 | 图片 4 | 建议阅读 7 分钟 | 评价反馈

JDK1.8 中 HashMap 如何应对 hash 冲突?

Java学习者社区

点击关注公众号,Java干货及时送达?

JDK1.8 中 HashMap 如何应对 hash 冲突?

来源:blog.csdn.net/weixin_43689776/

article/details/99999126

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值。

第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存储的位置如下图所示:

JDK1.8 中 HashMap 如何应对 hash 冲突?

执行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存储的位置如下图所示:

JDK1.8 中 HashMap 如何应对 hash 冲突?

相信大家已经看出区别了:

当数组长度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发生就讲解完毕了!

推荐阅读• MyBatis 批量插入几千条数据,请慎用foreach• spring boot集成kafka之spring-kafka深入探秘• mybatis-plus团队新作:mybatis-mate 轻松搞定数据权限• 一道面试题,GET 请求能传图片吗?最近面试BATJ,整理一份面试资料《Java面试BAT通关手册》,覆盖了Java核心技术、JVM、Java并发、SSM、微服务、数据库、数据结构等等。获取方式:点“在看”,关注公众号并回复 Java 领取,更多内容陆续奉上。

文章有帮助的话,在看,转发吧。

谢谢支持哟 (*^__^*)

继续阅读
weinxin
资源分享QQ群
本站是一个IT技术分享社区, 会经常分享资源和教程; 分享的时代, 请别再沉默!
沙海
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: