正在搜索不存在O（n）的值的哈希表？ （線性探測）

Question

試圖瞭解線性探測邏輯。

使用開放尋址作爲散列表，你怎麼能確認一個元素不在表中。

例如，假設你有一個10桶散列表。 假設你散列一個密鑰並插入它。現在，如果元素A和B將被插入並散列並減少到相同的桶，那麼如果使用線性探測器，則元素A和B可能彼此相鄰。

現在，僅僅因爲存儲桶是空的，似乎並不意味着地圖中不存在元素。例如您首先刪除元素A後搜索元素B.首先你會得到一個空桶，你期待B的存在，但是你需要再去探索一次，你會發現B，它確實存在。如果這個邏輯是正確的，那麼你不需要搜索整個表來確認一個密鑰是否不存在？即每次O（n）表演。

我說的是，你不需要通過整個地圖來真正確認它不存在嗎？

使用散列映射的單獨鏈接方法，該問題不存在。

編輯： 我的意思是在看這幅畫 http://upload.wikimedia.org/wikipedia/commons/b/bf/Hash_table_5_0_1_1_1_1_0_SP.svg

如果約翰·史密斯被刪除，我們試圖找到桑德拉·迪伊。

或者對於線性尋址，您的意思是移動元素以避免出現孔洞。即如果約翰·史密斯被刪除，如果152到154的元素被移回一個地方？它在描述中並沒有真正看到，但這可能會有一定意義。除了如上所述特德貝克加速到154而不是153。需要多一點工作，比我想象的多一點。

可能只是在每個存儲桶中使用簡單的鏈接列表。

Answer 1

在絕對最壞的情況下，是確定某個項目是否在表格中的算法是O（n）。但是，這不會發生在正確管理的哈希表中。

當一個項目被刪除時，一個墓碑應放置在它被刪除的表格槽位。墓碑只是一些數據，表明過去有一個元素，但它已被刪除。這樣，每次搜索元素時，都必須遵循所使用的任何探測序列，直到找到一個空的插槽。如果某個插槽爲空，則已完成該散列值的探測序列，並知道該插槽不會位於表格中的任何其他位置。

如果探針序列中沒有空插槽，則您必須搜索探針序列中的每個插槽的唯一方法是。既然你應該總是把哈希表的目標設定爲大約一半，這不應該發生。

Answer 2

使用散列表解決了與探測策略的衝突，對數據結構的刪除功能提出了嚴格的要求。當你刪除一個項目時，你必須補償散列表，以便它仍然滿足搜索需要（這是散列表的要點）。

使用線性探測，如果您刪除一個項目，您將移動到下一個插槽。如果它匹配我們剛剛刪除的插槽的散列，請將其移動。沖洗並重復，直到到達空槽。還有懶惰的刪除策略，其中項目被標記爲刪除，然後在下一次搜索時實際刪除/補償。

假設三個項目{A0，A1，A2}具有相同的哈希值。讓{A0，A1}在Hashtable中，{A2}不在。如果我們刪除A0，我們將其標記爲刪除。當我們搜索A2（不在Hashtable中）時，我們找到A0（刪除），然後我們移動到A1，我們將它移到A0的槽中，完成刪除操作。我們移動到下一個槽位（可能是A2，或A1槽位候選人正在佔用的位置），但發現它是空的，因此我們清除了A1剛剛騰空的槽位，並且我們的散列表回到了原始狀態。

Answer 3

我認爲這是遲到了，但有一個提到探測序列和哈希表的最大探測序列。

每次插入一個元素時，你都會記住過去已經做過的最大探測次數是多少，並且是'maxProb'小於你爲插入當前元素所做的探測次數。

最終，當您在散列表中搜索元素時，只會執行最大的maxProb搜索。

現在考慮到您不允許無限或N個探測器，其中N是散列表的容量，運行時間將爲O（x），其中x是最差情況下允許的最大探測器。

假設你的哈希鍵生成算法是這樣的，它迫使你多次探測，那麼你可以用這樣的方式實現數據結構，如果插入需要x個探測器，它應該考慮重新自我。