1什么是哈希冲突？我们知道HashMap底层是由数组+链表/红黑树组成的。当我们通过put(key,value)向hashmap中添加元素时，需要使用hash函数来确定元素应该放在哪里。在数组的哪个位置，当不同的元素放在数据相同的位置时，后面插入的元素会以链表的形式插入到前面元素的末尾。这时，我们称之为哈希冲突。2如何解决hash冲突实际上，根本不可能杜绝hash冲突的发生。我们能做的就是尽可能的降低hash冲突的概率：下面介绍HashMap中如何处理hash冲突？当我们将元素(key,value)放入hashmap中时，最终会执行putVal()方法，而在putVal()方法中，会执行hash(key)操作，并将执行结果作为一个putVal方法的参数。那么我们先看看hash(key)方法是干什么的。publicVput(Kkey,Vvalue){returnputVal(hash(key),key,value,false,true);}staticfinalinthash(Objectkey){inth;//判断key是否为null，如果为null则直接返回0；//如果不为null，则返回(h=key.hashCode())的执行结果^(h>>>16)return(key==null)?0:(h=key.hashCode())^(h>>>16);}(h=key.hashCode())^(h>>>16)执行三步操作：我们一步步分析：第一步：h=key.hashCode()这一步会根据key值计算出一个int类型的h值，即hashcode值，例如"helloWorld".hashCode()-->-1554135584"123456"。hashCode()-->1450575459"Ilovejava".hashCode()-->-1588929438至于hashCode()是如何根据key计算hashcode值的，需要分几种情况来分析：如果我们使用一个对象自己创建的，我们在没有重写hashCode()方法的情况下，会调用Object类的hashCode()方法，此时返回的是对象的内存地址值，所以如果对象不同，hashcode()计算出来的hashcode是不同的。如果使用java中定义的String、Integer等引用类型作为键，这些类一般会重写hashCode()方法。有兴趣的可以看看对应的源码。简单来说，Integer类的hashCode()返回的是一个Integer值，而String类型的hashCode()方法稍微复杂一些，这里就不展开了。总的来说，hashCode()方法的作用就是根据不同的key获取不同的hashCode值。JDK8系列教程：https://www.javastack.cn/cate...第2步：h>>>16这一步将第1步计算出的h值无符号右移16位。为什么要右移16位，当然是第三步了。第三步：h^(h>>>16)将hashcode值的高低16位异或（0同0，0同1，差1）得到hash值。例如：假设HIS：1290846991它的二进制数字是：01001100111100001100001111111：右转移后：00000000000000000000000000000000000000000000001111001110000不同或运行作为哈希。为什么要进行第二步和第三步呢？答案是减少哈希冲突！数组中存储的元素的位置由以下代码行确定：//对（数组的长度-1）和哈希值执行按位与运算：i=(n-1)&hash//i对应数组位置的索引n为当前数组的大小。我们将上面的步骤作为第四步，来比较执行1、2、3、4四步和只执行第一步和第四步的不同效果。.我们将两个元素node1(key1,value1)和node2(key2,value2)放入hashmap中，hashmap的数组长度为n=16。执行1、2、3、4四步：1.h=key.hashCode()假设计算结果为：h=3654061296对应的二进制数为：011011001110011010001100111100002.h>>>16h无符号权shift16位得到：000000000000000001101100111001103.hash=h^(h>>>16)异或运算得到hash：011011001111000011100000000001104.i=(n-1)&hashn-1=100shn100100对应的二进制数：:01101100111100001110000000000110hash&15:00000000000000000000000000000110转换为10-proof:&ENSP5I的值最终为5，也就是说Node1存放在索引为5的数组中。同理，我们对(key2,value2)进行同样的运算过程：1.h=key.hashCode()假设计算结果为：h=3652881648对应的二进制数为：011011001101110110001100111100002.h>>>16h无符号右移16位得到：000000000000000001101100110111013.hash=h^(h>>>16)异或运算得到hash：011011001111000011100000001011014.i=(n-1)&hashn-1=15对应二进制数：0000000000000000000000001111Hash：01101100111100001110000000101101hash&15:00000000000000000000000000001101转换为10-proof:&ENSP节点123的值和存储节点23的值存储位置如下图所示：执行1、4两步：1.h=key.hashCode()计算结果也是：h=3654061296对应的二进制数为：011011001110011010001100111100004.i=(n-1）＆hashn-=15相应的二进制编号：0000000000000000000000000000111111111HASH（H）：011011001110011010001100110000HASH＆15：0000000000000000000000000000000000000000000000000000000000000000000000000000000000：0为0。同理，我们对(key2,value2)进行同样的操作：1.h=key.hashCode()计算结果也是：h=3652881648对应的二进制数为：011011001101110110001100111100004.i=(n-1)&Hashn-1=15对应的二进制数：0000000000000000000000001111hash(h):011011000000000000011110000hash&15:00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002数组索引为0的node1和node2的存储位置如下图所示：相信大家已经看出区别了：当数组长度n较小时，n-1的二进制数高16位，所有位都为0，此时如果直接和H值进行&（按位与）运算，则只能使用h值的低16位数据。这时候hash冲突的可能性会大大增加，因为不同的h值转换成二进制后低16位是有可能相同的，如上例：h值key1.hashCode()和key2.hashCode()得到的不一样，一个h1=3654061296，一个h2=3652881648，可惜这两个h1和h2的低16位数字转换成二进制后完全一样，所以h1&(n-1)和h2&(n-1)会计算出相同的结果，这也导致node1和node2存放在数组索引相同的位置，发生hash冲突。当我们使用h^(h>>>16)进行运算时，会将h的高16位数据和低16位数据进行异或运算，最终的hash值高16位保留高16位数据h值，而hash值的低16位数据是h值的高低16位数据共同作用的结果。因此，即使h1和h2的低16位相同，最终计算出的哈希值的低16位也很可能不同，从而降低了哈希冲突的概率。ps：还有一个注意点：为什么是(n-1)？我们知道n是hashmap中数组的长度，那为什么要进行n-1次操作呢？答案也是为了减少哈希冲突的概率！要理解这一点，首先要知道HashMap规定数组的长度n必须是2的整数次方，至于为什么是2的整数次方，在扩展方法resize()中会详细说明的哈希图。因为n是2的整数次方，所以n一定是偶数。那么我们来比较一下i=hash&n和i=hash&(n-1)的异同。如果n是偶数，那么n转换成二进制后最低位一定为0，与hash按位与后最低位仍为0，导致i的值只能是一个偶数，这浪费了数组中的索引奇数空间也增加了散列冲突的可能性。所以我们要执行n-1得到一个奇数，这样n-1的低位转换成二进制后一定是1，而与hash按位与运算后的最低位可能是0也可能是1，这就是让i的值即可以是偶数也可以是奇数，充分利用数组的空间，减少hash冲突的概率。至此，关于JDK1.8中的HashMap如何减少存储元素时出现hash的讲解完毕！来源：blog.csdn.net/weixin_43689776/article/details/99999126近期热点文章推荐：1.1000+Java面试题及答案（2022最新版）2.厉害了！Java协程来了。..3.SpringBoot2.x教程，太全面了！4.不要用爆破爆满画面，试试装饰者模式，这才是优雅的方式！！5.《Java开发手册（嵩山版）》最新发布，赶快下载吧！感觉不错，别忘了点赞+转发！
