Java教程

哈希冲突笔记

本文主要是介绍哈希冲突笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

哈希冲突

哈希冲突的产生原因

但由于通过哈希函数产生的哈希值是有限的,而数据可能比较多,导致经过哈希函数处理后仍然有不同的数据对应相同的值。这时候就产生了哈希冲突。

解决哈希冲突的四种方法

1.开放地址方法

(1)线性探测

   按顺序决定值时,如果某数据的值已经存在,则在原来值的基础上往后加一个单位,直至不发生哈希冲突。 

(2)再平方探测

   按顺序决定值时,如果某数据的值已经存在,则在原来值的基础上先加1的平方个单位,若仍然存在则减1的平方个单位。随之是2的平方,3的平方等等。直至不发生哈希冲突。

(3)伪随机探测

   按顺序决定值时,如果某数据已经存在,通过随机函数随机生成一个数,在原来值的基础上加上随机数,直至不发生哈希冲突。

2.链式地址法(HashMap的哈希冲突解决方法)

对于相同的值,使用链表进行连接。使用数组存储每一个链表。

优点:

(1)拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;

(2)由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;

(3)而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间

开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间

(4)在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

缺点:

指针占用较大空间时,会造成空间浪费,若空间用于增大散列表规模进而提高开放地址法的效率。

3.建立公共溢出区

建立公共溢出区存储所有哈希冲突的数据。

4.再哈希法

对于冲突的哈希值再次进行哈希处理,直至没有哈希冲突。

 

这篇关于哈希冲突笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!