03、处理散列冲突的方法

处理散列冲突的方法

我们在使用 hash 函数之后发现关键字 key1 不等于 key2 ，但是 f(key1) = f(key2)，即有冲突，那么该怎么办呢？不急我们慢慢往下看。

开放地址法

了解开放地址法之前我们先设想以下场景。

菜馆内，铃铃铃，铃铃铃 电话铃响了

大鹏：厨子，给我订个包间，我今天要去带几个客户去你那谈生意。

厨子：大鹏啊，你常用的那个包间被人订走啦。

大鹏：厨子你这不仗义呀，咋没给我留住呀，那你给我找个空房间吧。

厨子：好滴老哥

哦，穿越回古代就没有电话啦，那看来穿越的时候得带着几个手机了。

上面的场景其实就是一种处理冲突的方法-----开放地址法

开放地址法就是一旦发生冲突，就去寻找下一个空的散列地址，只要列表足够大，空的散列地址总能找到，并将记录存入，为了使用开放寻址法插入一个元素，需要连续地检查散列表，或称为探查，我们常用的有线性探测，二次探测，随机探测。

线性探测法

下面我们先来看一下线性探测，公式：

f,(key) = ( f(key) + di ) MOD m（di = 1,2,3,4,5,6....m-1）

我们来看一个例子，我们的关键字集合为{12，67，56，16，25，37，22，29，15，47，48，21}，表长为 12，我们再用散列函数 f(key) = key mod 12。

我们求出每个 key 的 f(key)见下表

我们查看上表发现，前五位的 f(key) 都不相同，即没有冲突，可以直接存入，但是到了第六位 f(37) = f(25) = 1,那我们就需要利用上面的公式 f(37) = f (f(37) + 1 ) mod 12 = 2，这其实就是我们的订包间的做法。下面我们看一下将上面的所有数存入哈希表是什么情况吧。

我们把这种解决冲突的开放地址法称为线性探测法。下面我们通过视频来模拟一下线性探测法的存储过程。

另外我们在解决冲突的时候，会遇到 48 和 37 虽然不是同义词，却争夺一个地址的情况，我们称其为堆积。因为堆积使得我们需要不断的处理冲突，插入和查找效率都会大大降低。

通过上面的视频我们应该了解了线性探测的执行过程了，那么我们考虑一下这种情况，若是我们的最后一位不为 21，为 34 时会有什么事情发生呢？

此时他第一次会落在下标为 10 的位置，那么如果继续使用线性探测的话，则需要通过不断取余后得到结果，数据量小还好，要是很大的话那也太慢了吧，但是明明他的前面就有一个空房间呀，如果向前移动只需移动一次即可。不要着急，前辈们已经帮我们想好了解决方法

二次探测法

其实理解了我们的上个例子之后，这个一下就能整明白了，根本不用费脑子，这个方法就是更改了一下 di 的取值

线性探测： f,(key) = ( f(key) + di ) MOD m（di = 1,2,3,4,5,6....m-1）

二次探测： **f,(key) = ( f(key) + di ) MOD m（di =1^**2 , -1^**2 , 2^**2 , -2^**2 .... q^**2, (q^2, q<=m/2）

注：这里的是 -1^2，而不是 (-1)^2 一正一负，交替来的

所以对于我们的 34 来说，当 di = -1 时，就可以找到空位置了。

二次探测法的目的就是为了不让关键字聚集在某一块区域。另外还有一种有趣的方法，位移量采用随机函数计算得到，接着往下看吧.

随机探测法

大家看到这是不又有新问题了，刚才我们在散列函数构造规则的第一条中说

（1）必须是一致的，假设你输入辣子鸡丁时得到的是在看，那么每次输入辣子鸡丁时，得到的也必须为在看。如果不是这样，散列表将毫无用处。

咦？怎么又是在看哈哈，那么问题来了，我们使用随机数作为他的偏移量，那么我们查找的时候岂不是查不到了？因为我们 di 是随机生成的呀，这里的随机其实是伪随机数，伪随机数含义为，我们设置随机种子相同，则不断调用随机函数可以生成不会重复的数列，我们在查找时，用同样的随机种子，它每次得到的数列是相同的，那么相同的 di 就能得到相同的散列地址。

随机种子（Random Seed）是计算机专业术语，一种以随机数作为对象的以真随机数（种子）为初始条件的随机数。一般计算机的随机数都是伪随机数，以一个真随机数（种子）作为初始条件，然后用一定的算法不停迭代产生随机数

通过上面的测试是不是一下就秒懂啦，为什么我们可以使用随机数作为它的偏移量，理解那句，相同的随机种子，他每次得到的数列是相同的。

下面我们再来看一下其他的函数处理散列冲突的方法

再哈希法

这个方法其实也特别简单，利用不同的哈希函数再求得一个哈希地址，直到不出现冲突为止。

f,(key) = RH,( key ) (i = 1,2,3,4.....k)

这里的 RH,就是不同的散列函数，你可以把我们之前说过的那些散列函数都用上，每当发生冲突时就换一个散列函数，相信总有一个能够解决冲突的。这种方法能使关键字不产生聚集，但是代价就是增加了计算时间。是不是很简单啊。

链地址法

下面我们再设想以下情景。

袁记菜馆内，铃铃铃，铃铃铃电话铃又响了，那个大鹏又来订房间了。

大鹏：老袁啊，我一会去你那吃个饭，还是上回那个包间

厨子：大鹏你下回能不能早点说啊，又没人订走了，这回是老王订的

大鹏：老王这个老东西啊，反正也是熟人，你再给我整个桌子，我拼在他后面吧

不好意思啊各位同学，信鸽最近太贵了还没来得及买。上面的情景就是模拟我们的新的处理冲突的方法链地址法。

上面我们都是遇到冲突之后，就换地方。那么我们有没有不换地方的办法呢？那就是我们现在说的链地址法。

还记得我们说过得同义词吗？就是 key 不同 f(key) 相同的情况，我们将这些同义词存储在一个单链表中，这种表叫做同义词子表，散列表中只存储同义词子表的头指针。我们还是用刚才的例子，关键字集合为{12，67，56，16，25，37，22，29，15，47，48，21}，表长为 12，我们再用散列函数 **f(key) = key mod 12。**我们用了链地址法之后就再也不存在冲突了，无论有多少冲突，我们只需在同义词子表中添加结点即可。下面我们看下链地址法的存储情况。

链地址法虽然能够不产生冲突，但是也带来了查找时需要遍历单链表的性能消耗，有得必有失嘛。

公共溢出区法

下面我们再来看一种新的方法，这回大鹏又要来吃饭了。

袁记菜馆内.....

厨子：呦，这是什么风把你给刮来了，咋没开你的大奔啊。

大鹏：哎呀妈呀，别那么多废话了，我快饿死了，你快给我找个位置，我要吃点饭。

厨子：你来的，太不巧了，咱们的店已经满了，你先去旁边的小屋看会电视，等有空了我再叫你。小屋里面还有几个和你一样来晚的，你们一起看吧。

大鹏：电视？看电视？

上面得情景就是模拟我们的公共溢出区法，这也是很好理解的，你不是冲突吗？那冲突的各位我先给你安排个地方呆着，这样你就有地方住了。我们为所有冲突的关键字建立了一个公共的溢出区来存放。

那么我们怎么进行查找呢？我们首先通过散列函数计算出散列地址后，先于基本表对比，如果不相等再到溢出表去顺序查找。这种解决冲突的方法，对于冲突很少的情况性能还是非常高的。