发表文章

[最新] 解决哈希冲突的四种方法

flowerCSDN 2月前 1

版权声明:本文为博主原创文章,未经博主允许不得转载。 http://blog.csdn.net/flower_CSDN/article/details/82180305

1,开放地址法
就是为产生冲突的地址H(key)求得一个地址序列。
地址序列:

H0,H1,.....Hs   (1=<s<=m-1)

m为表的长度

H0=H(key)  (H(key)=key mod m)
Hi=H(H(key)+di) MOD m    (i=1,2,,,,,,s)

我怎么感觉这个式子不对啊!我觉得应该是Hi=H(H(key)+di)就好了啊!H(Key)不是mod m了嘛
其中di为增量,计算方法分为两种:
线性探测再散列和平方探测再散列
线性探测再散列 di = 1 , 2 , 3 , … , m-1
平方探测再散列 di = H(key)+(-1)^i * j^2 (i=1,2,…..s; j每次从1开始循环直到计算出存放它的位置)(我是这样推哒!~)
懒得写,画图啦!有点抽象啊!
大家看看这个就明白啦!http://blog.csdn.net/yeiweilan/article/details/73412438
2,链地址法
用数组+单链表的方式,HashMap和Hashtable底层就是这样解决哈希冲突的。
每个数组元素后面连接一个单链表用来存储哈希记录相同的元素。
哈希记录的计算方式:H(key)=key mod n
n为表长
3,再哈希
就是如果当前这个哈希函数计算出的哈希记录冲突了,然后再选用其它的哈希函数,直到不再冲突为止。
4,建立一个公共溢出区。
猜测:将所有冲突的元素放到一个公共的区域。

更为具体的看这个博主的吧!我是看完自己总结一遍,印象深刻点。
这个博主写的非常详细啊!
解决Hash冲突四种方法 - CSDN博客 http://blog.csdn.net/yeiweilan/article/details/73412438

相关推荐
最新评论 (0)
返回
发表文章
flowerCSDN
文章数
122
评论数
0
注册排名
460355