【C++、数据结构】哈希表——散列表(一)（概念/总结）

「前言」

个人主页： 代码探秘者
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.模拟实现哈希表

点击这里！