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() --> - "".hashCode() --> "我爱java".hashCode() --> - 至于hashCode()是如何根据key计算出hashcode值的，要分几种情况进行分析:
- 如果我们使用的自己创建的对象，在我们没有重写hashCode()方法的情况下,会调用Object类的hashCode()方法，而此时返回就是对象的内存地址值，所以如果对象不同，那么通过hashcode()计算出的hashcode就是不同的。
- 如果是使用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值为：
- 它的二进制数为：0 00001111
- 右移十六位之后：00000000 00000000 0
- 进行异或操作后：0
- 最终得到的hash值：
那么问题来了: 明明通过第一步得到的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 = - 对应的二进制数为:
0
2.h >>> 16
- h无符号右移16位得到：
00000000 00000000 0
3.hash = h ^ (h >>> 16)
- 异或操作后得到hash：
0 00000110
4.i = (n-1) & hash
- n-1=15 对应二进制数 :
00000000 00000000 00000000 00001111 - hash :
0 00000110 - hash & 15 :
00000000 00000000 00000000 00000110 - 转化为10进制 ：
&ensp 5
最终得到i的值为5，也就是说node1存放在数组索引为5的位置。
同理我们对(key2, value2) 进行上述同样的操作过程:
1.h = key.hashCode()
- 假设计算的结果为：
h = - 对应的二进制数为:
0
2.h >>> 16
- h无符号右移16位得到：
00000000 00000000 0
3.hash = h ^ (h >>> 16)
- 异或操作后得到hash：
0 00
4.i = (n-1) & hash
- n-1=15 对应二进制数 :
00000000 00000000 00000000 00001111 - hash :
0 00 - hash & 15 :
00000000 00000000 00000000 00001101 - 转化为10进制 ：
&ensp 13
最终得到i的值为13，也就是说node2存放在数组索引为13的位置
node1和node2存储的位置如下图所示:
执行1、4两个步骤:
1.h = key.hashCode()
- 计算的结果同样为：
h = - 对应的二进制数为:
0
4.i = (n-1) & hash
- n-1=15 对应二进制数 :
00000000 00000000 00000000 00001111 - hash(h) :
0 - hash & 15 :
00000000 00000000 00000000 00000000 - 转化为10进制 ：
0
最终得到i的值为0，也就是说node1存放在数组索引为0的位置
同理我们对(key2, value2) 进行上述同样的操作过程:
1.h = key.hashCode()
- 计算的结果同样为：
h = - 对应的二进制数为:
0
4.i = (n-1) & hash
- n-1=15 对应二进制数 :
00000000 00000000 00000000 00001111 - hash(h) :
0 - 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 = ，另一个h2 = ，但是不幸的是这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冲突发生的概率。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/176640.html原文链接：https://javaforall.net
