什么是哈希冲突

哈希就是做一个映射,为的是查找快.冲突是因为映射毕竟是有一个范围的,这个范围可能会小于你原来的那个范围,所以可能好多个值映射了之后成为一个值了.

举例来说,可能希望查找字符串比较快,你会用一种计算方法将一个字符串映射为一个整数,而且要求这个数字在100以内.那么如果处理了10000个字符串,他们映射的值肯定会冲突.

一文理解哈希冲突四种解决方法

哈希是通过对数据进行再压缩，提高效率的一种解决方法。但由于通过哈希函数产生的哈希值是有限的，而数据可能比较多，导致经过哈希函数处理后仍然有不同的数据对应相同的索引值。这时候就产生了 哈希冲突 （ 两个值都需要同一个地址索引位置 ）。

装填因子（装填因子=数据总数 / 哈希表长）、哈希函数、处理冲突的方法

其实也就是哈希表的实现 。

1.开放地址方法(再散列法)

可以通俗理解为所有的地址都对所有的数值开放，而不是链式地址法的封闭方式，一个数值固定在一个索引地址位置。

p1=hash(key)如果冲突就在p1地址的基础上+1或者散列处理，p2=hash(p1)....

（1）线性探测

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

（2）再平方探测

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

和线性探测相比就是改变探测了步长。因为如果都是+1来探测在数据量比较大的情况下，效率会很差。

（3）伪随机探测

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

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

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

优点：

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

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

（3）开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；

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

        缺点：

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

3.建立公共溢出区

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

4.再哈希法

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

可以理解为p=hash(key)如果冲突就p=hash2(key)....

参考文献：

文章1

视频（非常易懂）

什么是哈希冲突？

哈希计算就是努力的把比较大的数据存放到相对较小的空间中。

最常见的哈希算法是取模法。

下面简单讲讲取模法的计算过程。

比如：数组的长度是5。这时有一个数据是6。那么如何把这个

6存放到长度只有5的数组中呢。按照取模法，计算

6％5，结果是1，那么就把6放到数组下标是1的位置。那么，7

就应该放到2这个位置。到此位置，哈斯冲突还没有出现。

这时，有个数据是11，按照取模法，11％5＝1，也等于1。那么

原来数组下标是1的地方已经有数了，是6。这时又计算出1这个

位置，那么数组1这个位置，就必须储存两个数了。这时，就叫

哈希冲突。冲突之后就要按照顺序来存放了。

如果数据的分布比较广泛，而且储存数据的数组长度比较大。

那么哈希冲突就比较少。否则冲突是很高的。

具体的算法你要参照更加专业的书籍。

希望对你有帮助。

哈希冲突的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于什么是哈希冲突、哈希冲突的信息别忘了在本站进行查找喔。