動態完美雜湊

定義

動態完美雜湊被定義為一種解決雜湊表資料結構中衝突的程式設計方法。

應用

雖然這種方法比其雜湊表對應方法更佔用記憶體，但它非常適合需要對大量元素執行快速查詢、插入和刪除操作的情況。

實現

Dietzfelbinger 等人解釋了一種動態字典演算法，當一組 m 個專案被增量追加到字典中時，成員資格查詢始終消耗恆定時間，因此最壞情況時間為 O(1)，所需的總儲存空間為 O(m)（線性），並且插入和刪除的預期攤銷時間為 O(1)（攤銷常數時間）。在動態情況下，當一個鍵被插入到雜湊表中時，如果其在相應子表中的條目被佔用，則會發生衝突，並且子表將根據其新的總條目計數和隨機選擇的雜湊函式進行重建。由於二級表的負載因子保持較低，因此重建並不頻繁，並且插入的攤銷預期成本以及刪除的攤銷預期成本均為 O(1)。

此外，在動態情況下，頂級表或任何子表的最終大小事先並不知道。維護表預期 O(m) 空間的一種技術是在發生足夠多的插入和刪除操作時提示完全重建。只要插入或刪除的總數超過上次構建時元素的數量，透過考慮完全重新雜湊，插入和刪除的攤銷預期成本仍然為 O(1)。

Arnab Chakraborty

更新於: 2020年1月3日

673 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習