当前位置: 首页 > news >正文

深入理解开放寻址法中的三种探测序列

一、引言

开放寻址法是解决散列表中冲突的一种重要方法,当发生冲突(即两个不同的键通过散列函数计算得到相同的散列值)时,它会在散列表中寻找下一个可用的存储位置。而探测序列就是用于确定在发生冲突后,依次尝试哪些存储位置的规则。下面详细介绍线性探测、二次探测和双重散列这三种常见的探测序列。
在这里插入图片描述

二、线性探测(Linear Probing)

1. 原理

线性探测是最简单的开放寻址法探测序列。当插入一个键值对,计算出的散列值对应的存储位置已被占用时,它会按照顺序依次检查下一个存储位置(通常是逐个向后检查),直到找到一个空的存储位置为止。如果检查到散列表的末尾还没有找到空位置,就会从散列表的开头继续检查。其探测函数的公式为:
h ( k , i ) = ( h ′ ( k ) + i ) m o d m h(k, i) = (h'(k)+i) \bmod m h(k,i)=(h(k)+i)modm
其中, h ( k , i ) h(k, i) h(k,i) 是经过 i i i 次探测后得到的存储位置, h ′ ( k ) h'(k) h(k) 是初始的散列值(即通过散列函数直接计算得到的位置), i i i 是探测次数( i = 0 , 1 , 2 , ⋯ i = 0, 1, 2, \cdots i=0,1,2,), m m m 是散列表的大小。

2. 示例

假设散列表的大小 m = 10 m = 10 m=10,散列函数 h ′ ( k ) = k m o d 10 h'(k)=k \bmod 10 h(k)=kmod10。现在要依次插入键 23 23 23 33 33 33 43 43 43

  • 插入键 23 23 23 h ′ ( 23 ) = 23 m o d 10 = 3 h'(23)=23 \bmod 10 = 3 h(23)=23mod10=3,位置 3 3 3 为空,直接插入。
  • 插入键 33 33 33 h ′ ( 33 ) = 33 m o d 10 = 3 h'(33)=33 \bmod 10 = 3 h(33)=33mod10=3,位置 3 3 3 已被占用,进行第一次探测 i = 1 i = 1 i=1 h ( 33 , 1 ) = ( 3 + 1 ) m o d 10 = 4 h(33, 1)=(3 + 1)\bmod 10 = 4 h(33,1)=(3+1)mod10=4,位置 4 4 4 为空,插入到位置 4 4 4
  • 插入键 43 43 43 h ′ ( 43 ) = 43 m o d 10 = 3 h'(43)=43 \bmod 10 = 3 h(43)=43mod10=3,位置 3 3 3 已被占用,进行第一次探测 i = 1 i = 1 i=1 h ( 43 , 1 ) = ( 3 + 1 ) m o d 10 = 4 h(43, 1)=(3 + 1)\bmod 10 = 4 h(43,1)=(3+1)mod10=4,位置 4 4 4 也被占用,进行第二次探测 i = 2 i = 2 i=2 h ( 43 , 2 ) = ( 3 + 2 ) m o d 10 = 5 h(43, 2)=(3 + 2)\bmod 10 = 5 h(43,2)=(3+2)mod10=5,位置 5 5 5 为空,插入到位置 5 5 5
3. 优缺点
  • 优点:实现简单,只需要进行简单的加法和取模运算。
  • 缺点:容易产生“聚集”现象,即连续被占用的存储位置会越来越长,导致后续插入和查找操作的效率降低。

三、二次探测(Quadratic Probing)

1. 原理

二次探测通过二次函数来确定探测序列,它在发生冲突时,不是像线性探测那样逐个向后检查,而是按照二次方的步长来检查存储位置。其探测函数的公式为:
h ( k , i ) = ( h ′ ( k ) + c 1 i + c 2 i 2 ) m o d m h(k, i)=(h'(k)+c_1i + c_2i^2) \bmod m h(k,i)=(h(k)+c1i+c2i2)modm
其中, c 1 c_1 c1 c 2 c_2 c2 是正的常数, h ′ ( k ) h'(k) h(k) 是初始散列值, i i i 是探测次数( i = 0 , 1 , 2 , ⋯ i = 0, 1, 2, \cdots i=0,1,2,), m m m 是散列表的大小。常见的情况是 c 1 = c 2 = 1 c_1 = c_2 = 1 c1=c2=1

2. 示例

同样假设散列表的大小 m = 10 m = 10 m=10,散列函数 h ′ ( k ) = k m o d 10 h'(k)=k \bmod 10 h(k)=kmod10 c 1 = c 2 = 1 c_1 = c_2 = 1 c1=c2=1。要插入键 23 23 23 33 33 33 43 43 43

  • 插入键 23 23 23 h ′ ( 23 ) = 23 m o d 10 = 3 h'(23)=23 \bmod 10 = 3 h(23)=23mod10=3,位置 3 3 3 为空,直接插入。
  • 插入键 33 33 33 h ′ ( 33 ) = 33 m o d 10 = 3 h'(33)=33 \bmod 10 = 3 h(33)=33mod10=3,位置 3 3 3 已被占用,进行第一次探测 i = 1 i = 1 i=1 h ( 33 , 1 ) = ( 3 + 1 × 1 + 1 × 1 2 ) m o d 10 = 5 h(33, 1)=(3+1\times1 + 1\times1^2)\bmod 10 = 5 h(33,1)=(3+1×1+1×12)mod10=5,位置 5 5 5 为空,插入到位置 5 5 5
  • 插入键 43 43 43 h ′ ( 43 ) = 43 m o d 10 = 3 h'(43)=43 \bmod 10 = 3 h(43)=43mod10=3,位置 3 3 3 已被占用,进行第一次探测 i = 1 i = 1 i=1 h ( 43 , 1 ) = ( 3 + 1 × 1 + 1 × 1 2 ) m o d 10 = 5 h(43, 1)=(3+1\times1 + 1\times1^2)\bmod 10 = 5 h(43,1)=(3+1×1+1×12)mod10=5,位置 5 5 5 也被占用,进行第二次探测 i = 2 i = 2 i=2 h ( 43 , 2 ) = ( 3 + 1 × 2 + 1 × 2 2 ) m o d 10 = 9 h(43, 2)=(3+1\times2 + 1\times2^2)\bmod 10 = 9 h(43,2)=(3+1×2+1×22)mod10=9,位置 9 9 9 为空,插入到位置 9 9 9
3. 优缺点
  • 优点:一定程度上缓解了线性探测的“聚集”问题,因为它的探测步长是变化的。
  • 缺点:仍然可能出现二次聚集的情况,即不同的初始散列值可能会产生相同的探测序列。

四、双重散列(Double Hashing)

1. 原理

双重散列使用两个散列函数来确定探测序列。当发生冲突时,它会根据第二个散列函数计算出的步长来依次检查存储位置。其探测函数的公式为:
h ( k , i ) = ( h 1 ( k ) + i × h 2 ( k ) ) m o d m h(k, i)=(h_1(k)+i\times h_2(k)) \bmod m h(k,i)=(h1(k)+i×h2(k))modm
其中, h 1 ( k ) h_1(k) h1(k) 是第一个散列函数计算得到的初始散列值, h 2 ( k ) h_2(k) h2(k) 是第二个散列函数, i i i 是探测次数( i = 0 , 1 , 2 , ⋯ i = 0, 1, 2, \cdots i=0,1,2,), m m m 是散列表的大小。为了保证能够遍历散列表中的所有位置, h 2 ( k ) h_2(k) h2(k) 的值必须与 m m m 互质。

2. 示例

假设散列表的大小 m = 10 m = 10 m=10,第一个散列函数 h 1 ( k ) = k m o d 10 h_1(k)=k \bmod 10 h1(k)=kmod10,第二个散列函数 h 2 ( k ) = 7 − ( k m o d 7 ) h_2(k)=7-(k \bmod 7) h2(k)=7(kmod7)。要插入键 23 23 23 33 33 33 43 43 43

  • 插入键 23 23 23 h 1 ( 23 ) = 23 m o d 10 = 3 h_1(23)=23 \bmod 10 = 3 h1(23)=23mod10=3,位置 3 3 3 为空,直接插入。
  • 插入键 33 33 33 h 1 ( 33 ) = 33 m o d 10 = 3 h_1(33)=33 \bmod 10 = 3 h1(33)=33mod10=3,位置 3 3 3 已被占用, h 2 ( 33 ) = 7 − ( 33 m o d 7 ) = 7 − 5 = 2 h_2(33)=7-(33 \bmod 7)=7 - 5 = 2 h2(33)=7(33mod7)=75=2,进行第一次探测 i = 1 i = 1 i=1 h ( 33 , 1 ) = ( 3 + 1 × 2 ) m o d 10 = 5 h(33, 1)=(3+1\times2)\bmod 10 = 5 h(33,1)=(3+1×2)mod10=5,位置 5 5 5 为空,插入到位置 5 5 5
  • 插入键 43 43 43 h 1 ( 43 ) = 43 m o d 10 = 3 h_1(43)=43 \bmod 10 = 3 h1(43)=43mod10=3,位置 3 3 3 已被占用, h 2 ( 43 ) = 7 − ( 43 m o d 7 ) = 7 − 1 = 6 h_2(43)=7-(43 \bmod 7)=7 - 1 = 6 h2(43)=7(43mod7)=71=6,进行第一次探测 i = 1 i = 1 i=1 h ( 43 , 1 ) = ( 3 + 1 × 6 ) m o d 10 = 9 h(43, 1)=(3+1\times6)\bmod 10 = 9 h(43,1)=(3+1×6)mod10=9,位置 9 9 9 为空,插入到位置 9 9 9
3.优缺点
  • 优点:是开放寻址法中最好的方法之一,能更均匀地分布键,减少聚集现象,使插入、查找和删除操作的平均性能更接近理想情况。
  • 缺点:需要设计两个散列函数,实现相对复杂,计算开销也会稍微大一些。
http://www.lryc.cn/news/530847.html

相关文章:

  • 图像噪声处理技术:让图像更清晰的艺术
  • linux运行级别
  • 深入剖析Electron的原理
  • C++ 游戏开发:完整指南
  • WebForms SortedList 深度解析
  • 【hot100】刷题记录(12)-回文链表
  • 深入理解 Unix Shell 管道 Pipes:基础和高级用法 xargs tee awk sed等(中英双语)
  • [MySQL]事务的理论、属性与常见操作
  • RS485接口EMC
  • 快速上手mybatis教程
  • 本地部署DeepSeek-R1保姆级教程
  • blender 相机参数
  • 在GPIO控制器中,配置通用输入,读取IO口电平时,上拉和下拉起到什么作用
  • Maven工程核心概念GAVP详解:从命名规范到项目协作的基石
  • 如何利用DeepSeek打造医疗领域专属AI助手?从微调到部署全流程解析
  • Redis|前言
  • 眼见着折叠手机面临崩溃,三星计划增强抗摔能力挽救它
  • Leetcode面试高频题分类刷题总结
  • Vue.js `v-memo` 性能优化技巧
  • Altium Designer绘制原理图时画斜线的方法
  • 在K8S中,有哪几种控制器类型?
  • 什么是Rust?它有什么特点?为什么要学习Rust?
  • Golang 并发机制-3:通道(channels)机制详解
  • kamailio的kamctl的使用
  • HarmonyOS:ArkWeb进程
  • UI线程用到COM只能选单线程模型
  • LLMs之DeepSeek:Math-To-Manim的简介(包括DeepSeek R1-Zero的详解)、安装和使用方法、案例应用之详细攻略
  • 在C语言中使用条件变量实现线程同步
  • 图书管理系统 Axios 源码__新增图书
  • Maven全解析:从基础到精通的实战指南