数据结构中的通用散列

对于任何哈希函数，我们可以说如果表大小 m 远小于宇宙大小 u，那么对于任何哈希函数 h，都有一个 U 的大子集具有相同的哈希值。

为了解决这个问题，我们需要一组哈希函数，我们可以从中选择任何适合 S 函数。如果大多数哈希函数对 S 来说都更好，我们可以选择随机哈希函数

假设 ℌ 是哈希函数的一组。如果对于每个 x，y ∈ U，使得 h ∈ ℌ，h(x) = h(y)，数量至多为 |ℌ|/𝑚，那么我们可以说 ℌ 是通用的。换句话说，我们可以说对于从 ℌ 中随机选出的哈希函数 h，不同键 x 和 y 之间发生碰撞的概率不超过概率 1/m。如果 h(x) = h(y) 是从集合 {0, 1, . . ., m – 1} 中随机独立选出的，则会发生碰撞。

如果我们使用哈希函数 h 在哈希表中存储 S，那么搜索和删除的预期时间为 O(1 + α)。

阿纳布·查克拉博蒂

更新于: 8 月 10 日 2020

663 次观看

开启你的职业生涯

通过完成此课程来获得认证

开始