处理散列函数冲突的几种方法

一.  前言

在前面中文章中，我们介绍了散列方法和散列函数的相关知识，然而任一种散列函数也不能避免产生冲突，因此选择好的解决冲突的方法十分重要。为了减少冲突，对散列表加以改造。若设散列表HT有 m 个地址,  将其改为 m 个桶。其桶号与散列地址一一对应,  第 i (0≤i < m) 个桶的桶号即为第 i 个散列地址。解决散列函数的冲突方法有多种，总体分为闭散列方法和开散列方法两大类，如下：

二 .  闭散列方法

必散列方法又称开地址法，所有的桶都直接放在散列表数组中，并把该数组组织成环形结构，当出现冲突的时候，我们需要把冲突项存入一个空桶，寻找这个空桶的方法有很多，主要分为线性探查法、二次探测再散列、双散列法等等等

1.  线性探查法

发现冲突后，在表中顺次向后寻找“下一 个”空桶 存入

举例：

给出一组元素，他们的关键码是37,25,14,36,49,68,57,11,散列表为HT[12]，表m的大小 = 12,

采用散列函数的是：

Hash（x）= x % 11 //因为11是小于等于m最接近m的质数

这样可得结果如下图：

创建一个长度为12的数组，依次将上述散列地址存入数组：首先，

将37存入下标4的空间中

将25存入下标3的空间中

将14存入下标3的空间中，但是此时下标3的空间已经存储了25，4存储了37，发生冲突，则在表中顺次向后寻找“下一 个”空桶下标,5存入14

将36存入下标3的空间中，但是此时下标3的空间已经存储了25，4存储了37，5存储了14，发生冲突，则在表中顺次向后寻找“下一 个”空桶下标,6存入36

将49存入下标5的空间中，但是此时下标5的空间已经存储了36，6存储了36，发生冲突，则在表中顺次向后寻找“下一 个”空桶下标,7存入49

将68存入下标2的空间中

将57存入下标2的空间中，但是此时下标2,3,4,5,6都存储了其他数值，则在表中顺次向后寻找“下一 个”空桶下标8存入57

将11存入下标0的空间中，完成，如下图

2.  二次探测再散列

二次探测再散列又称平方探测法，在寻找空桶的时候，是按照后—>前—>后—>前的顺序寻找的

举例：

还是拿上面的例子来说，首先，

将37存入下标4的空间中

将25存入下标3的空间中

将14存入下标3的空间中，但是此时下标3的空间已经存储了25，则向后寻找，发现下标4存储了37，则向前寻找，存入下标为2的空间

将36存入下标3的空间中，但是此时下标3的空间已经存储了25，则向后寻找，发现下标4存储了37，则向前寻找，发现下标为2的空间存储了14，则继续向后寻找，存储下标为5的空间

将49存入下标5的空间中，但是此时下标5的空间已经存储了36，则向后寻找，存入下标为6的空间

将68存入下标2的空间中，发现下标2存储了14，则向后寻找，发现下标3存储了25，则向前寻找，存入下标为1的空间

将57存入下标2的空间中，发现下标2存储了14，则向后寻找，发现下标3存储了25，则向前寻找，发现下标1存储了68，则向后寻找，发现下标为3的空间存储了25，则向前寻找，存储下标0

将11存入下标0的空间中，发现下标0存储了57完成，发现下标1存储了68，则向前查找，存储下表为11的空间（环），完成，如下图：

三.  开散列方法

开散列方法首先对关键码集合用某一个散列函数计算它们的存放位置。

若设散列表地址空间的所有位置是从 0 到 m-1, 则关键码集合中的所有关键码被划分为m个子集, 具有相同地址的关键码归于同一子集。我们称同一子集中的关键码互为同义词。每一个子集称为一个桶。

通常各个桶中的表项通过一个单链表链接起来，称之为同义词子表。所有桶号相同的表项都链接在同一个同义词子表中，各链表的表头结点组成一个向量。

举例：

还是拿上面的例子举例，则利用开散列发处理冲突后，如下图：