JDK1.8 中 HashMap 如何应对 hash 冲突？
码农突围
共 4754字，需浏览 10分钟
·
2021-12-01 00:29
点击上方“码农突围”，马上关注
这里是码农充电第一站，回复“666”，获取一份专属大礼包 真爱，请设置“星标”或点个“在看
来源：blog.csdn.net/weixin_43689776/
article/details/99999126
1 什么是hash冲突
put(key, value)向hashmap中添加元素时，需要通过散列函数确定元素究竟应该放置在数组中的哪个位置，当不同的元素被放置在了数据的同一个位置时，后放入的元素会以链表的形式，插在前一个元素的尾部，这个时候我们称发生了hash冲突。2 如何解决hash冲突
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()
"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值。
第2步：h >>> 16
第3步：h ^ (h >>> 16)
假设h值为：1290846991 它的二进制数为：01001100 11110000 11000011 00001111 右移十六位之后：00000000 00000000 01001100 11110000 进行异或操作后：01001100 11110000 10001100 11110000 最终得到的hash值：1290833136
// 将(数组的长度-1)和hash值进行按位与操作:
i = (n - 1) & hash // i为数组对应位置的索引 n为当前数组的大小
node1(key1, value1)、node2(key2, value2)，hashmap的数组长度n=16。假设计算的结果为： h = 3654061296对应的二进制数为: 01101100 11100110 10001100 11110000
h无符号右移16位得到： 00000000 00000000 01101100 11100110
异或操作后得到hash： 01101100 11110000 11100000 00000110
n-1=15 对应二进制数 : 00000000 00000000 00000000 00001111hash : 01101100 11110000 11100000 00000110hash & 15 : 00000000 00000000 00000000 00000110转化为10进制 ： &ensp 5
假设计算的结果为： h = 3652881648对应的二进制数为: 01101100 11011101 10001100 11110000
h无符号右移16位得到： 00000000 00000000 01101100 11011101
异或操作后得到hash： 01101100 11110000 11100000 00101101
n-1=15 对应二进制数 : 00000000 00000000 00000000 00001111hash : 01101100 11110000 11100000 00101101hash & 15 : 00000000 00000000 00000000 00001101转化为10进制 ： &ensp 13
计算的结果同样为： h = 3654061296对应的二进制数为: 01101100 11100110 10001100 11110000
n-1=15 对应二进制数 : 00000000 00000000 00000000 00001111hash(h) : 01101100 11100110 10001100 11110000hash & 15 : 00000000 00000000 00000000 00000000转化为10进制 ： 0
计算的结果同样为： h = 3652881648对应的二进制数为: 01101100 11011101 10001100 11110000
n-1=15 对应二进制数 : 00000000 00000000 00000000 00001111hash(h) : 01101100 11110000 11100000 11110000hash & 15 : 00000000 00000000 00000000 00000000转化为10进制 ： 0
&（按位与）操作，那么只能利用到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)?
resize()里详细讲。i = hash & n和 i = hash & (n-1)有什么异同。-End-
最近有一些小伙伴，让我帮忙找一些 面试题 资料，于是我翻遍了收藏的 5T 资料后，汇总整理出来，可以说是程序员面试必备！所有资料都整理到网盘了，欢迎下载！
点击👆卡片，关注后回复【 面试题】即可获取
评论