「前言」
🌈个人主页: 代码探秘者
🌈C语言专栏:C语言
🌈C++专栏: C++ / STL使用以及模拟实现
🌈数据结构专栏: 数据结构 / 十大排序算法
🌈Linux专栏: Linux系统编程 / Linux网络编程(准备更新)
🌈喜欢的诗句:天行健,君子以自强不息.
🥙1.散列表的基本概念
- 散列表(哈希表,Hash Table):是⼀种数据结构。特点是:可以根据数据元素的关键字计算出它在散列表中的存储地址
- 散列函数(哈希函数):Addr=H(key) 建⽴了“关键字”→“存储地址”的映射关系。
例:某散列表的⻓度为13,散列函数 H(key)=key%13。依次将数据元素 19、14、23 插⼊散列表:
19%13=6
14%13=1
23%13=10
理想情况下,在散列表中查找⼀个元素的时间复杂度为O1
- 冲突:在散列表中插⼊⼀个数据元素时,需要根据关键字的值确定其存储地址,若该地址已经存储了其他元素,则称这种情况为“冲突(碰撞)
- 同义词:若不同的关键字通过散列函数映射到同⼀个存储地址,则称它们为“同义词”
*
关于冲突: - 减少冲突:构造更适合的散列函数,让各个关键字尽可能地映射到不同的存储位置,从⽽减少“冲突”
- 处理冲突:拉链法、开放定址法(包含四种探测方法)
🥙2.散列函数的构造
1.散列函数定义
- 散列函数(哈希函数):Addr=H(key) 建⽴了“关键字”→“存储地址”的映射关系。
2.设计散列函数注意点
设计散列函数时应该注意什么
3.常见的散列函数
1.除留余数法
-
除留余数法 —— H(key) = key % p
-
散列表表⻓为m,取⼀个不⼤于m但最接近或等于m的质数p
比如:m=15,15 不是素数,我找一个比它小的素数,13 或11
p选质数的原因:
- 原因:对质数取余,可以分布更均匀,从⽽减少冲突
2.直接定址法
- 直接定址法 —— H(key) = key 或 H(key) = a*key + b
- 其中,a和b是常数。这种⽅法计算最简单,且不会产⽣冲突。若关键字分布不连续,空位较多,则会造成存储空间的浪费
3.数字分析法
- 数字分析法 —— 选取数码分布较为均匀的若⼲位作为散列地址
4.平⽅取中法
- 平⽅取中法——取关键字的平⽅值的中间⼏位作为散列地址
4.总结
🥙3.处理冲突的方法
一.处理冲突-拉链法
- 拉链法(⼜称链接法、链地址法):把所有同义词”存储在⼀个链表中。
1.插入操作
例:若散列表⻓度为13,散列函数 H(key)=key%13,⽤拉链法解决冲突。依次插⼊关键字 {19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}
如何在散列表(拉链法解决冲突)中插⼊⼀个新元素?
- Step 1:结合散列函数计算新元素的散列地址
- Step 2:将新元素插⼊散列地址对应的链表(可⽤头插法,也可⽤尾插法)
2.插入操作的优化
- 新元素插⼊链表时,若能保持链表有序,可以略微提⾼“查找”效率。
3.查找元素
查找⻓度——在查找运算中,需要对⽐关键字的次数称为查找⻓度
- 查找成功
- 查找失败
默认只统计关键字对比次数(空指针次数-部分才要求)
4.删除操作
- 删除成功
- 删除失败
5.总结
二.处理冲突-开放定址法
- 开放定址法:如果发⽣“冲突”,就给新元素找另⼀个空闲位置。
- 为什么叫“开放定址”?—— ⼀个散列地址,既对同义词开放,也对⾮同义词开放。
探测方法:⽤什么规则确定“另⼀个空闲位置”
- di 表示第 i 次发⽣冲突时,下⼀个探测地址与初始散列地址的相对偏移量。
1.线性探测法
- 插入操作
2.平⽅探测法(⼆次探测法)
3.双散列法
例:⻓度为13的散列表状态如下图所示,散列函数 H(key)=key%13,采⽤双散列法解决冲突,假设hash2(key)=13-(key %13)
分析:插⼊元素1、查找元素1 的过程。
- 两个散列函数,第一个不行,开始使用第二个,计算di
4.伪随机序列法
4.查找操作(统一)
查找操作原理类似,根据探测序列依次对⽐各存储单元内的关键字。
- 若探测到⽬标关键字,则查找成功。
- 若探测到空单元,则查找失败。
5.删除操作
如何删除⼀个元素:
- Step 1:先根据散列函数算出散列地址,并对⽐关键字是否匹配。若匹配,则“查找成功”
- Step 2:若关键字不匹配,则根据“探测序列”对⽐下⼀个地址的关键字,直到“查找成功”或“查找失败”
- Step 3:若“查找成功”,则删除找到的元素
注:题⽬⼀定会说明具体是采⽤哪种探测序列(线性探测法、平⽅探测法、双散列法、伪随机序列法)
错误示范(注意-线性探测演示)
- 先找15,删15
- 再要删1(开始探测了,会发现,找到原来放15的地方遇到空,这样就停止探测了)
正确示范(逻辑删除)
- 删15
- 找1
注意
采⽤“开放定址法”(线性探测法、平⽅探测法、双散列法、伪随机序列法原)时,删除元素不能简单地将被删元素的空间置为空,否则将截断在它之后的探测路径,可以做⼀个“已删除”标记,进⾏逻辑删除。
- 逻辑删除:定义一个flag=1, 删除则变0。(避免查找操作探测时,本来存在的数,没查到就停止探测了)。
6.总结
三.扩展:关于四种方法的探测覆盖率
线性探测法:采⽤线性探测法,⼀定可以探测到散列表的每个位置
- 只要散列表中有空闲位置,就⼀定可以插⼊成功
- 理想情况下,若散列表表⻓=m,则最多发⽣ m-1 次冲突即可“探测”完整个散列表
平⽅探测法:采⽤平⽅探测法,⾄少可以探测到散列表中⼀半的位置
- 即便散列表中有空闲位置,也未必能插⼊成功
- 若散列表⻓度 m 是⼀个可以表示成4j + 3的素数(如 7、11、19),平⽅探测法就能探测到所有位置。
双散列法:未必能探测到散列表的所有位置。
-
双散列法的探测覆盖率取决于第⼆个散列函数hash2(key) 设计的是否合理。
-
若hash2(key) 计算得到的值与散列表表⻓m互质,就能保证双散列发可以探测所有单元
伪随机序列法:di 是⼀个伪随机序列,由程序员⼈为设计
- 采⽤伪随机序列法,是否能探测到散列表中全部位置,取决于伪随机序列的设计是否合理
总结
🥙4.模拟实现哈希表
点击这里!