資料結構中的通用雜湊

對於任何雜湊函式，我們可以說如果表大小 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 次觀看

開啟你的職業生涯

透過完成此課程來獲得認證

開始