【数据结构】处理散列冲突的方法

ゞ浴缸里的玫瑰 2022-06-16 02:38 280阅读 0赞

> 摘自大话数据结构

我们设计得再好的散列函数也不可能完全避免冲突，这就像我们再健康也只能尽量预防疾病，但却无法保证永远不得病一样，既然冲突不能避免，就要考虑如何处理它。

那么当我们在使用散列函数后发现两个关键字key1≠key2，但是却有f(key1) = f(key2)，即有冲突时，怎么办呢？我们可以从生活中找寻思路。

试想一下，当你观望很久很久，终于看上一套房打算要买了，正准备下订金，人家告诉你，这房子已经被人买走了，你怎么办？对呀，再找别的房子呗！这其实就是一种处理冲突的方法开放定址法。

# 开放地址法 #

所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

它的公式是：

fi(key) = (f(key)+di) MOD m (di=1,2,3,......,m-1)

比如说，我们的关键字集合为\{12,67,56,16,25,37,22,29,15,47,48,34\},表长为12。 我们用散列函数f(key) = key mod l2。

当计算前5个数\{12,67,56,16,25\}时，都是没有冲突的散列地址，直接存入：

![图示][SouthEast]

计算key = 37时，发现f(37) = 1，此时就与25所在的位置冲突。

于是我们应用上面的公式f(37) = (f(37)+1) mod 12 = 2。于是将37存入下标为2的位置。这其实就是房子被人买了于是买下一间的作法：。

![图示][SouthEast 1]

接下来22,29,15,47都没有冲突，正常的存入：

![图示][SouthEast 2]

到了 key=48，我们计算得到f(48) = 0，与12所在的0位置冲突了，不要紧，我们f(48) = (f(48)+1) mod 12 = 1，此时又与25所在的位置冲突。于是f(48) = (f(48)+2) mod 12=2，还是冲突……一直到 f(48) = (f(48)+6) mod 12 = 6时，才有空位，机不可失，赶快存入：

![图示][SouthEast 3]

我们把这种解决冲突的开放定址法称为**线性探测法**。

从这个例子我们也看到，我们在解决冲突的时候，还会碰到如48和37这种本来都不是同义词却需要争夺一个地址的情况，我们称这种现象为**堆积**。很显然，堆积的出现，使得我们需要不断处理冲突，无论是存入还是査找效率都会大大降低。

考虑深一步，如果发生这样的情况，当最后一个key=34，f(key)=10,与22所在的位置冲突，可是22后面没有空位置了，反而它的前面有一个空位置，尽管可以 不断地求余数后得到结果，但效率很差。

因此我们可以改进di = 12, -12, 22, -22,……, q2, -q2 (q <= m/2),这样就等于是可以双向寻找到可能的空位置。

对于34来说，我 们取di即可找到空位置了。另外增加平方运算的目的是为了不让关键字都聚集在某一块区域。我们称这种方法为**二次探测法**。

![图示][SouthEast 4]

还有一种方法是，在冲突时，对于位移量 di 采用随机函数计算得到，我们称之为**随机探测法**。

此时一定会有人问，既然是随机，那么查找的时候不也随机生成办吗？如何可以获得相同的地址呢？这是个问题。这里的随机其实是伪随机数。

伪随机数是说，如果我们设置随机种子相同，则不断调用随机函数可以生成不会重复的数列，我们在査找时，用同样的随机种子，它每次得到的数列是相同的，相同的 di 当然可以得到相同的散列地址。

![图示][SouthEast 5]

总之，开放定址法只要在散列表未填满时，总是能找到不发生冲突的地址，是我们常用的解决冲突的办法。

# 再散列函数法 #

对于我们的散列函数来说，我们事先准备多个散列函数。

![图示][SouthEast 6]

这里RHi 就是不同的散列函数。每当发生散列冲突的时候，就换一个散列函数计算，相信总会有一个可以吧冲突解决掉。这种方法能够使得关键字不聚集，当然，相应地也增加了计算的时间。

# 链地址法 #

思路还可以再缓一缓，为什么有冲突就要换地方，我们直接在原地想办法可以吗？于是就有了链地址法。

将所有关键字为同义词的记录存储在一个单链表中，我们称这种表为同义词表，在散列中只存储所有同义词子表的头指针。对于关键字\{12,67,56,16,25,37,22,29,15,47,48,34\}，我们用前面同样的余数12位除数，进行除留余数法，可得到如下图所示的结构。此时，已经不存在什么冲突换址的问题了，无论有多少冲突，都只是在当前位置给单链表增加节点即可。

![图示][SouthEast 7]

链地址法对于可能会造成很多冲突的散列来说，提供了绝不会出现找不到地址的保障。当然，这也就带来了查找时需要遍历单链表的性能损耗。

# 公共溢出区法 #

这个方法其实就更加好理解，你不是冲突吗？好吧，凡是冲突的都跟我走，我给你们这些冲突找个地儿待着。这就如同孤儿院收留所有无家可归的孩子一样，我们为所有冲突的关键字建立了一个公共的溢出区来存放。

就前面的例子而言，我们共有三个关键字\{37,48,34\}与之前的关键字位置有冲突，那么就将它们存储到溢出表中。

![图示][SouthEast 8]

在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行比对，如果相等，则查找成功；如果不相等，则到溢出表去进行顺序查找。如果相对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。

[SouthEast]: /images/20220616/100b2c84e7d8465cadb21da0fc1b72d9.png
[SouthEast 1]: /images/20220616/f8e5b093b1b34cfb922ebe8e79eb83d5.png
[SouthEast 2]: /images/20220616/ada52e65d9ec4b75a2c7c8e7df3588c0.png
[SouthEast 3]: /images/20220616/31ffa1fc31cc4c4f9077816f4aeb8b36.png
[SouthEast 4]: /images/20220616/05527d3a716d4e3191151f3679841201.png
[SouthEast 5]: /images/20220616/7f1d1e57d953451f9c2dcc79865fd477.png
[SouthEast 6]: /images/20220616/89012c0c50624a93baf7bc685604462e.png
[SouthEast 7]: /images/20220616/81843e24eeeb41e68eafaad9d669fc1a.png
[SouthEast 8]: /images/20220616/49d329880eb34862bd524215f823fdee.png