闡述衝突解決策略的優缺點

下面解釋了一些衝突解決技術的優缺點：

獨立鏈式雜湊

獨立鏈式雜湊是一種雜湊技術，其中使用列表來處理衝突。因此，在同一位置有多個元素，它們在一個列表中。序列以連結串列的形式維護。

獨立鏈式雜湊的優點如下：

  • 獨立鏈式技術對錶的大小不敏感。

  • 思想和實現都很簡單。

獨立鏈式雜湊的缺點如下：

  • 在獨立鏈式中，鍵分佈不均勻。

  • 獨立鏈式可能導致表中出現空隙。

  • 位置中的列表可能非常長。

線性探測

線性探測是一種簡單的衝突解決技術，用於解決雜湊表（用於維護雜湊表中值的集合的資料結構）中的衝突。如果鍵值的位 置發生衝突，則線性探測技術會將下一個可用空間分配給該值。

線性探測的優點如下：

  • 線性探測需要的記憶體很少。

  • 它不太複雜，實現起來也比較簡單。

線性探測的缺點如下：

  • 線性探測會導致一種稱為“主要聚集”的現象，其中雜湊表中存在大量被佔用的單元。

  • 線性探測中的值傾向於聚集，這使得探測序列更長。

二次探測

二次探測也是一種衝突解決機制，它接收由雜湊函式生成的初始雜湊值，並繼續從生成的函式中新增任意二次多項式的連續值，直到找到一個空閒槽來放置值。

二次探測的優點如下：

  • 二次探測不太可能出現主要聚集問題，並且比雙雜湊更容易實現。

二次探測的缺點如下：

  • 二次探測存在次要聚集。當兩個鍵雜湊到同一位置時，它們具有相同的探測序列。因此，在進行插入之前可能需要多次嘗試。

  • 而且探測序列不會探測表中的所有位置。

雙雜湊

雙雜湊也是當兩個不同的待搜尋值產生相同的雜湊鍵時的衝突解決技術。

它使用雜湊函式生成的雜湊值作為起點，然後透過一個間隔遞增位置，該間隔使用第二個獨立的雜湊函式確定。因此，這裡有兩個不同的雜湊函式。

雙雜湊的優點如下：

  • 雙雜湊最終克服了聚集問題。

雙雜湊的缺點如下：

  • 雙雜湊比其他任何方法都更難實現。

  • 雙雜湊可能導致抖動。

更新於：2021年7月8日

瀏覽量 10K+

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告