我的博客
欢迎来到我的博客
bunny.icu

哈希冲突的解决方法

哈希冲突的解决方法

哈希冲突的解决方法

开放定址法

使用某种探测算法在散列表中寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到。

实现方式有:
1. 线性探查再散列:发生hash冲突时,顺序查找下一个位置,直到找到一个空位置。d_i=+1,+2,+3,…
2. 二次/平方探查再散列:在发生hash冲突时,在表的左右位置进行按一定步长跳跃式探测。d_i=+1^2,-1^2,+2^2,-2^2,…
3. 伪随机探测再散列:有一个固定的随机数序列,在发生hash冲突时,将要存储的数据加上下一个随机数再散列,直到找到一个空位置。

再哈希法

构造多个哈希函数,当产生冲突时,计算另一个哈希函数的值。
这种方法不易产生聚集,但增加了计算时间。

链地址法 / 拉链法

链地址法又称为拉链法。
将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。
链地址法适合经常进行插入和删除的情况。
Java的HashMap和HashSet采用这种方式解决哈希冲突,同时对同义词链使用红黑树,提高查找和修改的效率。

建立公共溢出区

将哈希表分为公共表和溢出表,当溢出发生时,将所有溢出数据统一放到溢出区。

参考资料

Hash冲突及解决办法 – 51CTO
解决hash冲突的三个方法 – 博客园
解决哈希冲突的常用方法分析

版权声明


本作品系原创, 转载须遵循 CC BY-NC-ND 4.0 许可协议
本文标题:哈希冲突的解决方法
本文链接:https://www.bunny.icu/archives/1490

推荐文章

发表评论

textsms
account_circle
email

bunny.icu

哈希冲突的解决方法
哈希冲突的解决方法 开放定址法 使用某种探测算法在散列表中寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到。 实现方式有: 1. 线性探查再散列:发生hash冲突时,顺…
扫描二维码继续阅读
2022-08-06