数据结构中的 Brent 方法

在本节，我们将了解 Brent 方法与开放寻址哈希有关的知识。这种方法是一种启发式。它旨在尽可能减少哈希表中成功搜索的平均时间。

这种方法最初应用于双重哈希技术，但它可用于任何开放寻址技术，例如线性探测和二次探测。在开放寻址哈希表中存储的元素 x 的年龄是满足 x 位于 A[x_i] 中最小的值 i。

Brent 方法试图最小化所有元素的总年龄。如果我们插入元素 x，那么它会遵循以下步骤——我们找到 i 的最小值，使得 A[x_i] 为空，这是传统开放寻址会插入 x 的位置。现在考虑一个元素 y，存储在 A[x_i-2] 中。该元素存在于那里是因为 yj = x_i-2，某个值 j ≥ 0。我们检查数组位置 A[y_j+1] 是否为空，那么我们会将 y 移动到位置 A[y_j+1]，并在位置 A[x_i-2] 存储 x。

与普通的开放寻址相比，该方法将总年龄减少了 1。通常，Brent’s 方法针对每个 2 ≤ k ≤ i、数组项 A[x_i-k] 进行检查，查看是否存储了元素 y，该方法可以移动 y 到 A[y_j+1]、A[y_j+2]、……、A[y_j+k-1] 中的任何一个，以便为 x 腾出空间。

阿纳布·查克拉博蒂

更新于：2020 年 8 月 10 日

518 次观看

开启您的 职业生涯

通过完成课程获得认证

入门