資料結構中的羅賓漢雜湊

在本節中，我們將瞭解什麼是羅賓漢雜湊方案。這種雜湊是開放定址的一種技術。它嘗試透過使用更公平的碰撞解決策略來均衡元素的搜尋時間。在嘗試插入時，如果我們希望在位置 xi 處插入元素 x，並且已經將元素 y 放置在 y_j = x_i 處，那麼兩個元素中較年輕的元素必須繼續。因此，如果 i ≤ j，我們將嘗試在位置 x_i+1、x_i+2 等處插入 x。否則，我們將把 x 儲存在位置 x_i 處，並嘗試在位置 y_j+1、y_j+2 等處插入 y。

據 Devroye 等人表明，在最初的大小為 𝑚 = Α𝑛 的空表上執行 n 次插入操作後，使用羅賓漢插入演算法，最壞情況搜尋時間的期望值是 −

$$E[W]=\Theta(log\:log\:n)$$

並且其界限很緊。因此，這種演算法是開放定址的一種形式，具有雙對數最壞情況搜尋時間。

Arnab Chakraborty

更新於：11-Aug-2020

312 次檢視

開啟 事業

完成課程，獲得認證

開始學習