大家好,又见面了,我是你们的朋友全栈君。
在实际的应用中,选取合适的哈希函数可减少冲突,但冲突是不可避免的。所以我就想给大家说几种解决哈希冲突的方法啦~
首先就是开放定址法,用这个方法处理冲突的核心思想就是在冲突发生的时候,形成一个地址序列,顺着这个序列挨个去检查探测,一直等到找到一个“空”的开放地址。把我们发生冲突的关键字值存放到这个“空”地址中去。这个地址的算法一般就是:Hi=(H(key)+di)%m 这里面的i=1,2,。。。k。k要<=m-1;i是探测次数。不难理解,H(key)是关键字是key的哈希函数,加上di(每次再探测时的地址增量)对这个哈希表的长度做取余数的运算。根据di的取法不同,就可以得到不同的开放地址处理冲突探测的方法~
形成探测序列的方法很多,比如线性探测法、二次探测法、双哈希函数探测法。
二次探测法的地址增量序列为di=1^2,-1^2,2^2,-2^2,….q^2,-q^2,(q小于等于m/2,i为d的下标),这是一种较好的处理冲突的方法,它能够避免“聚集”现象。它的缺点就是不能探测到哈希表上的所有存储单元,但至少能探测到一半的存储单元。
双哈希函数探测法:Hi=(H(key)+i*RH(key))%m (i=1,2,…,m-1).其中,H(key),RH(key)是两个哈希函数,m为哈希长度。这个方法使用两个哈希函数,先用第一个函数H(key)对关键字计算哈希地址,一旦产生地址冲突,在用第二个函数RH(key)确定移动的步长因子,最后,通过步长因子序列由探测函数寻找空余的哈希地址。
那我就只说线性探测咯,比较基础易懂。
线性探测法:当哈希函数产生的数据元素的哈希地址中已有数据元素存在时,就是发生了冲突,从下一地址序列中寻找可以用的存储空间来存储数据元素。
关于线性探测法,我们举个例子吧!
假设有一个关键字集合,S={16,76,63,57,40},使用哈希法存储该集合,选取的哈希函数为:h(K)=K%m,即用数据元素的关键字K去整除哈希表的长度m,取余数作为存储该数据元素的哈希地址,其中,K和m均为正整数,并m要大于等于集合长度n。此时,n=5,m=11,所以每个元素的哈希地址以此为5,10,8,2,7.吧这几个数就放到0~10中相应数字的位置。这个时候,向刚刚构造的哈希表中插入27,50两个元素。若发生冲突就用线性探测发处理。27的哈希地址为5,已经被占用,接着探查下一个,即下标为6的存储单元,该单元空,所以把27放在6里,这个时候再看50的哈希地址为6,6已经被27占用,就接着探查下一个,发现7被40占用,就继续探测,一直到9,发现空闲,就把50放在9里。
线性再散列法是形式最简单的处理冲突的方法。插入元素时,如果发生冲突,算法会简单的从该槽位置向后循环遍历hash表,直到找到表中的下一个空槽,并将该元素放入该槽中(会导致相同hash值的元素挨在一起和其他hash值对应的槽被占用)。查找元素时,首先散列值所指向的槽,如果没有找到匹配,则继续从该槽遍历hash表,直到:(1)找到相应的元素;(2)找到一个空槽,指示查找的元素不存在,(所以不能随便删除元素);(3)整个hash表遍历完毕(指示该元素不存在并且hash表是满的)
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/149888.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...