本篇文章介绍如何利用二次探测法处理散列冲突。散列是一种将节点按关键字的散列地址存储在散列表中的过程。我们在散列的过程中,会发生将不同的关键字映射到同一个散列地址的现象,那么这个时候我们可以使用二次探测法来处理冲突。
工具/原料
纸,笔
智慧的大脑
方法/步骤
1
我们先来了解一下,二次探测法的增量序列。如下图所示。
![如何用二次探测法处理散列冲突](https://exp-picture.cdn.bcebos.com/8a17b3042e6817e93e71d94bd356d53da924ce27.jpg)
2
若当前扫描的元素的地址已经有元素了,那么,当前元素就保存在该地址的后移偏量。如下图所示。
![如何用二次探测法处理散列冲突](https://exp-picture.cdn.bcebos.com/dda98e4800fc77f7b5da8893c8715fdb3720906b.jpg)
3
现在我们来看这样一个序列。如下图所示。
![如何用二次探测法处理散列冲突](https://exp-picture.cdn.bcebos.com/94af5fc1b727ac532390499f2ecadce8914899af.jpg)
4
接下来我们将所有元素对11取余。如下图所示。
![如何用二次探测法处理散列冲突](https://exp-picture.cdn.bcebos.com/cca2552c56ee7b7f7b30a4c66ef4fcf5ef0d4196.jpg)
5
我们现在来创建一个散列表,如下图所示。
![如何用二次探测法处理散列冲突](https://exp-picture.cdn.bcebos.com/2e66f9ef28066b01d974ebf33df39187021cf33c.jpg)
6
现在根据取余的值将元素放入散列表。如下图所示。
![如何用二次探测法处理散列冲突](https://exp-picture.cdn.bcebos.com/27725684cde34b2cad38a3cc0d0e7c75e4f4436e.jpg)
7
其中47,7,11,16,92这些元素是根据取余的值直接放入散列表的。而29取余的值为7,7的位置上已经有元素了,那么我们放在7+1^2的位置上。3取余的值是3,3的位置上也已经有元素了,那么我们看3+1^2上也有元素,再看3-1^2的位置上没有元素,那么我们现在就放在这里。那么其他元素也是一样的道理。
![如何用二次探测法处理散列冲突](https://exp-picture.cdn.bcebos.com/a68c126efbf202b317cb40c830f4da5873dadbb3.jpg)
注意事项
感觉有帮助的话,记得点个赞哟
温馨提示:经验内容仅供参考,如果您需解决具体问题(尤其法律、医学等领域),建议您详细咨询相关领域专业人士。免责声明:本文转载来之互联网,不代表本网站的观点和立场。如果你觉得好欢迎分享此网址给你的朋友。转载请注明出处:https://www.i7q8.com/jiaoyu/2090.html