資料結構中雙重雜湊

在本節中，我們將瞭解開放定址方案中的雙重雜湊技術是什麼。有一個普通的雜湊函式 h´(x) : U → {0, 1, . . ., m – 1}。在開放定址方案中，當空間不為空時採用普通的雜湊函式 h’(x)，然後執行另一個雜湊函式來獲取某些插入空間。

$$h_{1}(x)=x\:mod\:m$$

$$h_{2}(x)=x\:mod\:m^{\prime}$$

$$h(x,i)=(h^{1}(x)+ih^{2})\:mod\:m$$

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}

$$h_{1}(x)=x\:mod\:20$$

$$h_{2}(x)=x\:mod\:13$$

x h(x, i) = (h1 (x) + ih2(x)) mod 20 

雜湊表 

阿納布·查克拉巴蒂

更新於： 2020 年 8 月 10 日

3K+ 瀏覽

開啟你的職業生涯

完成本課程即可獲得認證

開始