数据结构中的乘法哈希

以下我们将讨论乘法哈希方法。为此我们使用哈希函数 −

ℎ(𝑥) = ⌊𝑚𝑥𝐴⌋ 𝑚𝑜𝑑 𝑚

其中 A 是实际值的常量。此方法的优点是 m 的值不太关键。m 也可以是 2 的幂。虽然 A 的任何值都可以得到哈希函数，但是某些 A 的值比其他值好。

根据克努特，我们可以使用黄金分割来得到 A，因此 A 为

$$A=\frac{\sqrt5-1}{2}=0.61803398$$

当然，无论为 A 选择什么值。笼统原则表明，如果 u ≥ nm，那么将有一个散列值 i 和一些大小为 n 的 S ⊆ U，使得 h(x) = i 对于 S 中的所有 x。

因此，我们可以说，乘法的最坏情况哈希和除法的哈希一样糟糕。

Arnab Chakraborty

更新日期： 2020 年 8 月 10 日

906 次浏览

开启你的职业生涯

完成课程认证

开始