数据结构中的溢出处理

当一个新对 (键，元素) 的主桶已满时，就会发生溢出。

我们可以通过以下方式解决溢出问题：

以某种系统的方式搜索哈希表，找到一个未满的桶。

• 线性探测（线性开放寻址）。
• 二次探测。
• 随机探测。

允许每个桶都维护一个列表，其中包含所有以它为主桶的对，从而消除溢出。

• 数组线性列表。
• 链。

开放寻址是为了确保所有元素都直接存储在哈希表中，因此它尝试通过实施各种方法来解决冲突。

线性探测通过将数据放置在表中下一个空闲槽中来解决冲突。

线性探测的性能

• 最坏情况下的查找/插入/删除时间为 θ(m)，其中 m 表示表中对的数量。
• 当所有对都位于同一个簇中时，就会发生这种情况。

线性探测的问题

• 标识符倾向于聚集在一起
• 相邻的簇倾向于合并
• 增加或提高搜索时间

二次探测

线性探测搜索桶 (H(x)+i2)%b；H(x) 表示 x 的哈希函数

二次探测使用 i 的二次函数作为增量

检查桶 H(x)、(H(x)+i2)%b、(H(x)-i2)%b，其中 1<=i<=(b-1)/2

b 表示一个形如 4j+3 的素数，其中 j 是一个整数

随机探测

随机探测结合了随机数。

H(x):= (H’(x) + S[i]) % b
S[i] is a table along with size b-1
S[i] is indicated as a random permutation of integers [1, b-1].

Arnab Chakraborty

更新于: 2020年1月8日

7K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

立即开始