数据结构中整数键的哈希表

这里，我们将讨论带整数键的哈希表。这里，键值 𝑥 来自于如下集合 𝑈：𝑈 = {0, 1, … , 𝑢 – 2, 𝑢 – 1}。哈希函数是 ℎ。此哈希函数的域是 𝑈。范围位于集合 {0, 1, … , 𝑚 – 1} 中，并且 𝑚 ≤ 𝑢。

如果对于 𝑆 ⊆ 𝑈 中的每个 𝑥 ∈ 𝑆，ℎ(𝑥) 都唯一，则称哈希函数 h 是集合 𝑆 的完美哈希函数。如果 𝑚 = |𝑆|，则表示 𝑆 的完美哈希函数 ℎ 为最小值。因此，ℎ 是 S 和 {0, 1, … , 𝑚 – 1} 之间的双射。显然，最小完美哈希函数是理想的，因为它允许我们将 S 中的所有元素都存储在长度为 n 的单个数组中。

遗憾的是，即使 m 远大于 n，完美哈希函数也非常罕见。如果 S 中的每个元素都均匀且独立地映射到 {0, 1, ... , 𝑚 – 1} 中的随机元素，则根据生日悖论，如果 m 远小于 n²，则几乎肯定会存在 S 的两个元素，哈希值相同。

Arnab Chakraborty

更新日期：2020 年 8 月 10 日

277 次浏览

开启你的 职业生涯

完成课程获得认证

入门