資料結構中的乘法雜湊

以下我們將討論乘法雜湊方法。為此我們使用雜湊函式 −

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

其中 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 次瀏覽

開啟你的職業生涯

完成課程認證

開始