資料結構中的二次探測

在本節中，我們將會了解什麼是開放定址方案中的二次探測技術。有一個普通雜湊函式 h’(x) : U → {0, 1, . . ., m – 1}。在開放定址方案中，實際雜湊函式 h(x) 採用普通雜湊函式 h’(x)，並附加另一個部分形成一個二次方程。

h´ = (𝑥) = 𝑥 𝑚𝑜𝑑 𝑚

ℎ(𝑥, 𝑖) = (ℎ´(𝑥) + 𝑖2)𝑚𝑜𝑑 𝑚

我們還可以使用某些常量設定其他二次方程

i 的值為 0, 1, . . ., m – 1。因此，我們從 i = 0 開始，並不斷增加 i，直至找到一個空閒空間。所以最初當 i = 0 時，則 h(x, i) 等於 h´(x)。

示例

我們有一個大小為 20（m = 20）的列表。我們希望以線性探測的方式新增某些元素。這些元素為 {96, 48, 63, 29, 87, 77, 48, 65, 69, 94, 61}

 

雜湊表 

更新於：2020 年 8 月 10 日

7 千次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告