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 --> 458290771@qq.com
喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑💻
感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏
1. 拉链法
1.1 插入
如何插入？
- 结合散列函数计算新元素的散列地址
- 将新元素插入散列地址对应的链表（头插法、尾插法）
1.2 查找
如何查找？
- 先计算地址
- 再对链表中的元素进行对比
1.3 删除
如何删除？
- 先查找元素
- 如果能找到，就可以删除
2. 开放定址法
2.1 基本原理
根据散列函数 H ( k e y ) H(key) H(key)，求得初始散列地址。若发生冲突，如何找到“另一个空闲位置？”
H i = ( H ( k e y ) + d i ) % m H_i=(H(key)+d_i)\%m Hi=(H(key)+di)%m
H i H_i Hi —— 发生第 i 次冲突时的散列地址
H ( k e y ) H(key) H(key) —— 初始散列地址
d i d_i di —— 偏移量
m m m —— 散列表表长
四种常用方法构造探测序列 d i 。注： 0 ≤ i ≤ m − 1 d_i。注：0 \leq i \leq m-1 di。注：0≤i≤m−1
- 线性探测法 —— d i = 0 , 1 , 2 , 3 , . . . , m − 1 d_i=0,1,2,3,...,m-1 di=0,1,2,3,...,m−1
- 平方探测法 —— d i = 0 2 , 1 2 , − 1 2 , 2 2 , − 2 2 , . . . , k 2 , − k 2 。其中 k ≤ m / 2 d_i=0^2,1^2,-1^2,2^2,-2^2,...,k^2,-k^2。其中k\leq m/2 di=02,12,−12,22,−22,...,k2,−k2。其中k≤m/2
- 双散列法 —— d i = i ∗ h a s h 2 ( k e y ) 。其中 h a s h 2 ( k e y ) 是另一散列函数 d_i = i * hash_2{(key)}。其中hash_2(key)是另一散列函数 di=i∗hash2(key)。其中hash2(key)是另一散列函数
- 伪随机序列法 —— d i d_i di是一个伪随机序列，如 d i = 1 , 1 , 4 , 5 , 1 , 4 , . . . d_i=1,1,4,5,1,4,... di=1,1,4,5,1,4,...
特别注意：关于删除操作
采用开放定址法时，删除元素不能简单地将被删除元素的空间置为空，否则将阶段在它之后的探测路径，可以做一个“已删除”标记，进行逻辑删除