資料結構中整數鍵的雜湊表

這裡，我們將討論帶整數鍵的雜湊表。這裡，鍵值 𝑥 來自於如下集合 𝑈：𝑈 = {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 次瀏覽

開啟你的 職業生涯

完成課程獲得認證

入門