数据结构中的线性寻址法

本节中，我们将了解在开放寻址方案中什么是线性探测法。有一个普通的哈希函数 h’(x) : U → {0, 1, . . ., m – 1}。在开放寻址方案中，实际的哈希函数 h(x) 采用普通的哈希函数 h’(x) 并将其附加一些其他部分，以构成一个线性方程。

h’(𝑥) = 𝑥 𝑚𝑜𝑑 𝑚

ℎ(𝑥, 𝑖) = (ℎ’(𝑥) + 𝑖)𝑚𝑜𝑑 𝑚

i| 的值 = 0, 1, . . ., m – 1。因此，我们从 i = 0 开始，并增加它，直至我们获得一个可用空间。因此，最初当 i = 0 时，则 h(x, i) 与 h’(x) 相同。

示例

假设我们有一个大小为 20 的链表 (m = 20)。我们想使用线性探测法放置一些元素。元素为 {96, 48, 63, 29, 87, 77, 48, 65, 69, 94, 61}

 

哈希表 

更新于：2020 年 8 月 10 日

7000+ 浏览量

开启您的职业生涯

完成课程获得认证

开始学习
广告