数据结构中的罗宾汉哈希

在本节中，我们将了解什么是罗宾汉哈希方案。这种哈希是开放寻址的一种技术。它尝试通过使用更公平的碰撞解决策略来均衡元素的搜索时间。在尝试插入时，如果我们希望在位置 xi 处插入元素 x，并且已经将元素 y 放置在 y_j = x_i 处，那么两个元素中较年轻的元素必须继续。因此，如果 i ≤ j，我们将尝试在位置 x_i+1、x_i+2 等处插入 x。否则，我们将把 x 存储在位置 x_i 处，并尝试在位置 y_j+1、y_j+2 等处插入 y。

据 Devroye 等人表明，在最初的大小为 𝑚 = Α𝑛 的空表上执行 n 次插入操作后，使用罗宾汉插入算法，最坏情况搜索时间的期望值是 −

$$E[W]=\Theta(log\:log\:n)$$

并且其界限很紧。因此，这种算法是开放寻址的一种形式，具有双对数最坏情况搜索时间。

Arnab Chakraborty

更新于：11-Aug-2020

312 次查看

开启 事业

完成课程，获得认证

开始学习