資料結構中的非對稱雜湊

在本節中，我們將學習什麼是非對稱雜湊技術。在此技術中，散列表被拆分為 d 個塊，每個拆分長度為 n/d。探測值 xi，0 ≤ i ≤ d，從 $$\lbrace\frac{i*n}{d},...,\frac{(i+1)*n}{d-1}\rbrace$$ 中均勻提取。與多選雜湊一樣，要插入 x，演算法將檢查列表 A[x0], A[x1], . . ., A[xd – 1] 的長度。然後將 x 附加到這些列表中最短的一個。如果出現平局，則將 x 插入具有最小索引的列表中。

根據 Vocking，非對稱雜湊最長列表的預期長度為 −

$$E[W]\leq\frac{ln\:ln\:n}{d\:ln\:\phi_{2}}+O(1)$$

函式 𝜙𝑑 是黃金比例的推廣，因此 $$\phi_{2}=\frac{(1+\sqrt{5})}{2}$$

更新於: 11-8-2020

220 次瀏覽

開啟你的 職業

透過完成課程獲得認證

開始吧
廣告