解决Hash（哈希表）冲突的四种方案-Toy模板网

这篇具有很好参考价值的文章主要介绍了解决Hash（哈希表）冲突的四种方案。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

解决Hash（哈希）冲突的四种方案

参考&鸣谢

解决哈希冲突必须知道的几种方法小僵鱼

你还应该知道的哈希冲突解决策略 vivo互联网技术

解决哈希冲突的三种方法 kaleidoscopic

每日一题(哈希表及哈希冲突解决办法) 和笙

哈希是一种通过对数据进行压缩, 从而提高效率的一种解决方法，但由于哈希函数有限，数据增大等缘故，哈希冲突成为数据有效压缩的一个难题。本文主要介绍哈希冲突、解决方案，以及各种哈希冲突的解决策略上的优缺点。

哈希冲突即不同key值产生相同的地址，即发生了hash冲突。一般来说，哈希冲突是无法避免的，所以就有了解决方案。

常见的解决Hash冲突的方案有开放寻址法、链地址法和再哈希法。

原理是当发生hash冲突时，会以当前地址为基准，然后根据寻址方法（探查寻址），去寻找下一次地址。若依旧发生冲突，则继续寻址，直到找到一个空的位置为止。通用的散列函数形式为：

Hi=（H（key）+di）% m （i=1，2，…，n）

其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。

顺序查找表的下一个单元，直到找到一个空单元或查遍全表。

即当hash值为3冲突时(假设此时hash表长度为11)，利用线性探查的过程为：

H1 = (3+1)%11 = 4，此时若4依旧冲突，则再hash，即

H2 = (3+2)%11 = 5 … 通过这种线性增长增量系列，直到找到空的位置为止。

这种方法的特点是，当哈希冲突时，在表的左右进行跳跃探测，比较灵活。

此时di = 1^2, -1^2, 2^2, -2^2 …

假设当hash值为3冲突时(假设此时hash表长度为11)，利用二次探查的过程为：

H1 = (3+1^2)%11 = 4,此时若4依旧冲突，则再hash,即

H2 = (3+(-1)^2)%11 = 2 …

通过该方法直到找到空位置为止。

这种方法即是产生一些随机系列值，并给定随机数作为起点。

假设当hash值为3冲突时(假设此时hash表长度为11)，利用伪随机探测的过程为：

假设产生的随机系列为2，5，9 …，则

H1 = (3+2)%11 = 5

H2 = (3+5)%11 = 8

通过该方法直到找到空位置为止。

HashMap，HashSet其实都是采用的拉链法来解决哈希冲突的，就是在每个位桶实现的时候，我们采用链表（jdk1.8之后采用链表+红黑树）的数据结构来去存取发生哈希冲突的输入域的关键字（也就是被哈希函数映射到同一个位桶上的关键字）。首先来看使用拉链法解决哈希冲突的几个操作：

插入操作：在发生哈希冲突的时候，我们输入域的关键字去映射到位桶（实际上是实现位桶的这个数据结构，链表或者红黑树）中去的时候，我们先检查带插入元素x是否出现在表中，很明显，这个查找所用的次数不会超过装载因子（n/m : n为输入域的关键字个数，m为位桶的数目），它是个常数，所以插入操作的最坏时间复杂度为O(1)的。
查询操作：和插入操作一样，在发生哈希冲突的时候，我们去检索的时间复杂度不会超过装载因子，也就是检索数据的时间复杂度也是O(1)的
删除操作：如果在拉链法中我们想要使用链表这种数据结构来实现位桶，在删除一个元素x的时候，需要更改x的前驱元素的next指针的属性，把x从链表中删除。这个操作的时间复杂度也是O(1)的。

解决哈希冲突的方式,数据结构与算法,哈希算法,散列表,数据结构