07-7.5.3 处理冲突的方法

👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> [e-mail]

---

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

1. 拉链法

1.1 插入

如何插入？

1. 结合散列函数计算新元素的散列地址
2. 将新元素插入散列地址对应的链表（头插法、尾插法）

1.2 查找

如何查找？

1. 先计算地址
2. 再对链表中的元素进行对比

1.3 删除

如何删除？

1. 先查找元素
2. 如果能找到，就可以删除

2. 开放定址法

2.1 基本原理

根据散列函数 $H(key)$，求得初始散列地址。若发生冲突，如何找到“另一个空闲位置？”
$$H_i=(H(key)+d_i)\%m$$
$H_i$ —— 发生第 i 次冲突时的散列地址
$H(key)$ —— 初始散列地址
$d_i$ —— 偏移量
$m$ —— 散列表表长

四种常用方法构造探测序列 $d_i。注：0\le i\le m-1$

1. 线性探测法 —— $d_i=0,1,2,3,...,m-1$
2. 平方探测法 —— $d_i=0^2,1^2,-1^2,2^2,-2^2,...,k^2,-k^2。其中k\le m/2$
3. 双散列法 —— $d_i=i\ast has{h}_2(key)。其中has{h}_2(key)是另一散列函数$
4. 伪随机序列法 —— $d_i$是一个伪随机序列，如 $d_i=1,1,4,5,1,4,...$

特别注意：关于删除操作

采用开放定址法时，删除元素不能简单地将被删除元素的空间置为空，否则将阶段在它之后的探测路径，可以做一个“已删除”标记，进行逻辑删除