线性探测法处理散列冲突

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

工具/原料

    纸,笔

    智慧的大脑

方法/步骤

    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

注意事项

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

温馨提示:经验内容仅供参考,如果您需解决具体问题(尤其法律、医学等领域),建议您详细咨询相关领域专业人士。
免责声明:本文转载来之互联网,不代表本网站的观点和立场。如果你觉得好欢迎分享此网址给你的朋友。
转载请注明出处:https://www.i7q8.com/jiaoyu/2127.html

打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023年07月12日
下一篇 2023年07月12日
single-end

热门百科

single-end

相关推荐

  • 线性探测法处理散列冲突

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

    2023年07月12日
    0℃
  • 如何用二次探测法处理散列冲突

    如何用二次探测法处理散列冲突,本篇文章介绍如何利用二次探测法处理散列冲突。散列是一种将节点按关键字的散列地址存储在散列表中的过程。我们在散列的过程中,会发生将不同的关键字映射到同一个散列地址的现象,那么这个时候我们可以使用二次探测法来处理冲突。...

    2023年07月12日
    0℃
关注微信