本篇经验主要讲述如何使用线性探测法处理散列冲突。主要针对数据结构进行学习。接下来一起来看一下吧。

工具/原料

纸，笔

智慧的大脑

方法/步骤

1

我们直接用例子来讲述。如下图所示，d是我们第一次将数据放入不成功时的地址增量，每次加1。



2

我们首先将关键码集对11取余。如下图所示。



3

我们准备表长度为11的散列表。如下图所示。



4

根据取余的值将关键码放入相应的地址中。取余结果为几，地址就是几。



5

同时将每一个关键码需要进行几次放置写在关键码下方。比如我们29取余的值是7，但是7的位置上已经有关键码了，那么我们放置第一次的时候没有成功，那么根据增量，我们看7+1的位置还没有关键码，那么我们第二次放置时就成功了，下方就标上2。



6

接下来我们计算散列表的成功平均查找长度。我们将刚刚在下方标好的数字相加，将该值除以关键码个数9。因为我们这里是查找成功的平均查找长度，我们并不查找散列表中的空格，所以是除以9。



7

那么不成功的平均查找长度我们该如何计算呢？比如我们查找散列表中并不存在的关键码1。我们从第0位开始查找，遇到空格停止需要查找3次；从第1位开始查找，遇到空格停止需要查找2次。依此类推，我们查找的次数即为3+2+1+8+7+6+5+4+3+2+1.将计算所得值除以11。



8

遇到空格停止是因为假如我们寻找的关键码32取余的值是10，我们寻找10的位置是空格，那么我们就可以知道10后面的位置肯定没有取余为10的值的。32的第一个地址是10, 10的位置是空格，那么散列表中是不会有32的。

END

注意事项

制作不易，感觉有帮助的话，就点个赞吧