数据结构中的二次探测

在本节中，我们将会了解什么是开放寻址方案中的二次探测技术。有一个普通哈希函数 h’(x) : U → {0, 1, . . ., m – 1}。在开放寻址方案中，实际哈希函数 h(x) 采用普通哈希函数 h’(x)，并附加另一个部分形成一个二次方程。

h´ = (𝑥) = 𝑥 𝑚𝑜𝑑 𝑚

ℎ(𝑥, 𝑖) = (ℎ´(𝑥) + 𝑖2)𝑚𝑜𝑑 𝑚

我们还可以使用某些常量设置其他二次方程

i 的值为 0, 1, . . ., m – 1。因此，我们从 i = 0 开始，并不断增加 i，直至找到一个空闲空间。所以最初当 i = 0 时，则 h(x, i) 等于 h´(x)。

示例

我们有一个大小为 20（m = 20）的列表。我们希望以线性探测的方式添加某些元素。这些元素为 {96, 48, 63, 29, 87, 77, 48, 65, 69, 94, 61}

 

哈希表 

更新于：2020 年 8 月 10 日

7 千次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告