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