對于哈希表，正如我們所熟悉的那樣，我們首先計算哈希函數(shù)。然后我們需要處理碰撞；當(dāng)兩個或多個鍵插入散列到同一索引時的情況。執(zhí)行此操作的兩種方法包括單獨鏈接和線性探測。我的問題又來了，哪種方法刪除成本更低？我最初的想法是，如果線性探測中的簇很大，并且我們想要在簇中早期刪除某些鍵，則將所有鍵重新插入到已刪除鍵的右側(cè)可能會變得昂貴。如果這個陳述完全有效，是否有足夠的理由假設(shè)單獨的鏈接在刪除方面比線性探測更有效？
1 回答
呼啦一陣風(fēng)
TA貢獻(xiàn)1802條經(jīng)驗 獲得超6個贊
在線性探測的情況下，刪除會影響對具有早于清空單元的哈希值但存儲在晚于清空單元的位置的其他鍵的搜索?？盏膯卧駮?dǎo)致這些搜索錯誤地報告密鑰不存在。因此，當(dāng)一個單元格被清空時，有必要向前搜索表格中的后續(xù)單元格，直到找到另一個空單元格或可以移動到該單元格的鍵，并且該過程需要繼續(xù)下去，直到找到一個空單元格。
但是單獨鏈接的情況下，我們只需要從鏈表中刪除值，并且從鏈表中刪除值比線性探測情況下的上述過程容易得多。
添加回答
舉報
0/150
提交
取消