数据结构中的除法哈希

这里我们将讨论除法哈希。为此，我们使用以下哈希函数：

ℎ(𝑥) = 𝑥 𝑚𝑜𝑑 𝑚

为了使用此哈希函数，我们维护一个数组 A[0, … m – 1]。其中数组的每个元素都是指向链接列表头的指针。链接列表 Li 指向数组元素 A[i]，包含所有满足 h(x) = i 的元素 x。这种技术被称为链地址法。

在这种哈希表中，如果我们想要插入一个元素 x，这将花费 O(1) 的时间。我们计算索引 i = h(x)。然后将 x 追加或预先添加到列表 Li 中。如果我们想要搜索或删除一个元素，这个过程并不容易。我们必须找到索引 i = h(x)。然后遍历列表 Li，直到我们到达所需的值或列表耗尽。此操作花费的时间与列表 Li 的大小成正比。如果我们的集合 S 有 0、m、2m、3m、…、nm 个元素，那么存储在 L0 中的所有元素将需要线性时间来搜索和删除。

这种情况非常罕见。例如，如果 S 在全集 U 中均匀且独立地分布，并且 u 是 m 的倍数，则每个列表 Li 的预期大小仅为 n/m。在这种情况下，搜索和删除花费 O(1 + α) 的时间。为了避免上述情况，我们必须明智地选择 m。通常，我们避免将 m 设为 2 的幂。建议将 m 设为一个不接近 2 的幂的素数。

更新于： 2020年8月10日

476 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告