Java基础-Hash冲突的三种解决方案

这个问题是从HashMap引申出来的,遇到Hash冲突问题,该如何解决?

什么是Hash冲突?

设定 : 有一个空的数组
入参 : 一个key值,一个value值
操作 : 调用hash()方法, 计算出key的hash值,将hash值作为下标,在数组对应位置写入value值
冲突 : 如果两个不同的key计算出来的hash值相同,可是同一个下标只能存放一个value值,这样就产生了冲突
由于数组是容量是有限的,但是可以存入多个key,这样难免就会遇到hash冲突问题
解决Hash冲突主要有三种方法:

1. 开放地址法
2. 再散列法
3. 拉链法(链地址法)

开放地址法

核心思想:如果当前位置发生了Hash冲突,就在数据里找寻其他没有冲突的位置存放这个数据
简单地说,就是如果当前数组位置已经有数据了,就去看看它下一个位置是否是空的,如果是,就可以插入啦,如果不是,就需要继续访问在下一个位置,直到找到空的位置. 可以将数组想成一个循环数组,找到最后一位后,从第一位再继续开始,也就是说,如果当前位置为 i, 数组大小是m, 那么
查找范围是:

i+1, i+2, i+3 ... m-1, 0 , 1, 2 ... i -1 计算公式是: Hi=（H（key）+di）% m i=1，2，…，n

开放地址法在具体找寻下一个节点计算上根据di的取值方式,又有多种方法实现

1⃣️线性探测法

di = 1，2，3，…，m-1

如上文所诉就是线性探测法, 如果当前下标i已经有数据了(发生冲突了), 就去访问相邻的下一个位置,即i+1这个位置是否是空的,如果有数据,再访问i+2, 直到找到空的位置, 或者循环一圈发现无法找到空位置,这时候表明数组已经被存满了, 需要进行数组的扩容操作

这个方法会产生 聚集 问题:
当很多个key计算出的都是一个hash值,那么根据这个规则, 数组里将会有连续很长一段位置都存放了数据,这就产生了 聚集 , 这时新进来一个key, 同样也是这个hash值的时候,就需要从当前位置逐个遍历到聚集的末尾才能插入,当哈希表越来越满时聚集越来越严重，这导致产生非常长的探测长度，后续的数据插入将会非常费时。通常数据超过三分之二满时性能下降严重，因此设计哈希表关键确保不会超过这个数据容量的一半，最多不超过三分之二

2⃣️平方探测法
$di = 1^2, -1^2, 2^2, -1^2, ... k^2, -k^2 (k <= m / 2)$di=12,−12,22,−12,...k2,−k2(k<=m/2)
虽然平方探测法解决了线性探测法的一次聚集，但是它也有一个小问题，就是关键字key散列到同一位置后探测时的路径是一样的,这样对于许多落在同一位置的关键字而言，越是后面插入的元素，探测的时间就越长,这种现象被称作“二次聚集(secondary clustering)”,其实这个在线性探测法里也有,这种现象出现的原因是由于对于落在同一个位置的关键字我们采取了一个依赖 i 的函数（i或者i^2）来进行探测，它不会因为key的不同或其他因素而改变探测的路径
为了解决这个这个问题, 我们将路径依赖key,使用再hash的形式定位

再散列法

我们可以再弄另外一个Hash函数，对落在同一个位置的关键字进行再次的Hash,探测的时候就用依赖这个Hash值去探测,由于Hash2函数不同于Hash1,所以两个不同的关键字Hash1值和Hash2值同时相同的概率就会变得非常低。这样就避免了二次聚集，但同时也付出了计算另一个散列函数Hash2的代价

拉链法(链地址法)

最后,就是我们常用的拉链法了, 在HashMap中就是通过这种形式解决Hash冲突的
原理:
当数组上的某个节点发生Hash冲突时,就把这个节点作为头节点,将新插入的节点挂到这个节点上,形成一个连表,新来的节点通过尾插的形式逐个插入节点

这样查找和插入的效率都非常高,缺点就是会增加多空间
还有一个问题: 如果插入的数据key都是同一个Hash值,那么造成数组其他位置没有数据,某一个节点上挂了很长的一个链表,导致效率变慢,HashMap的在JDK8的优化方式是当某个节点上的链表长度>=8的时候,就会将链表变成红黑树来提高查找效率,具体的可参见HashMap源码(1.8版本)

好啦~ 今天的分享就到这里 欢迎评论交流~~~