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值的,要分几种状况进行剖析:
- 如果咱们应用的本人创立的对象,在咱们没有重写hashCode()办法的状况下,会调用Object类的hashCode()办法,而此时返回就是对象的内存地址值,所以如果对象不同,那么通过hashcode()计算出的hashcode就是不同的。
- 如果是应用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开发手册(嵩山版)》最新公布,速速下载!
感觉不错,别忘了顺手点赞+转发哦!