資料結構中的線性定址法

本節中，我們將瞭解在開放定址方案中什麼是線性探測法。有一個普通的雜湊函式 h’(x) : U → {0, 1, . . ., m – 1}。在開放定址方案中，實際的雜湊函式 h(x) 採用普通的雜湊函式 h’(x) 並將其附加一些其他部分，以構成一個線性方程。

h’(𝑥) = 𝑥 𝑚𝑜𝑑 𝑚

ℎ(𝑥, 𝑖) = (ℎ’(𝑥) + 𝑖)𝑚𝑜𝑑 𝑚

i| 的值 = 0, 1, . . ., m – 1。因此，我們從 i = 0 開始，並增加它，直至我們獲得一個可用空間。因此，最初當 i = 0 時，則 h(x, i) 與 h’(x) 相同。

示例

假設我們有一個大小為 20 的連結串列 (m = 20)。我們想使用線性探測法放置一些元素。元素為 {96, 48, 63, 29, 87, 77, 48, 65, 69, 94, 61}

 

雜湊表 

更新於：2020 年 8 月 10 日

7000+ 瀏覽量

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告