如何刪除哈希表中的O（1）雙鏈接鏈接？

我已經看過一兩個線程，但我仍然不認爲它已經完全清理了所以...如何刪除哈希表中的O（1）雙鏈接鏈接？

我一直在尋找哈希表中的鏈接在算法簡介（第11）。他們說，如果一個哈希表的鏈表被雙鏈接，那麼刪除可以在O（1）時間內執行。但我看不出如此如此。

T is a chained hash table. I want to delete element X from it. 
h(X.key) returns the hash of X's key. 
So, to delete X, pass X to the delete routine. 
Then we can find X's slot in the linked list: 
T[ h(X.key) ] = j 
j is actually the pointer to the head of the linked list as > 1 key hashes to j. 
So we still need to now search the linked list at j to find X to delete it, 
regardless of whether or not the list is doubly linked. 
And this search is O(n). So deletion is O(n)???

我的觀點是，我們是否還需要搜索鏈接列表中的X？ X是我們想要存儲在散列表中的任意對象。它不包含指針。 鏈接列表中包含X的元素將包含指向鏈接列表中下一個元素和前一個元素的指針，但不包含X.

來源

2014-11-13 Boon

在這裏深入挖掘之後，我偶然發現了答案。

本書中的隱含假設是鏈接列表中的鏈接是元素X的一部分，而不是單獨的實現鏈接並指向元素的容器節點對象。也就是說，我們希望移除的對象X包含指向鏈表中下一個和前一個元素的指針。作者真的應該明確這一點。

感謝RBarryYoung的答案！

來源

2014-11-16 13:56:33 Boon

如果你這樣想，這是有道理的。但在現實生活中，您將對象存儲到哈希表中，而不是包含對象的節點以及指向其前一節點和下一節點的指針。因此，除非您嘗試構建LinkedHashMap（Java），否則不太有用。 – Alex

散列表上的插入和刪除都是O（1）。鏈接列表必須是正確的這意味着任何操作都可能需要多個操作。關鍵是，這個鏈接只有在散列函數有衝突時纔會發生。如果碰撞是例行的，刪除將是O（n）。在算法教科書中，插圖說明了這種工作方式可能會顯示相對較少的桶數，但是碰撞次數的平均值爲而不是隨n增長，只有最差的情況。

來源

2014-11-13 22:18:53 brycem

我的主要困惑之處在於：如果我將對象X或其關鍵字傳遞給刪除例程，例程仍然需要在鏈接列表中找到X，然後才能刪除它。在最壞的情況下，在這裏找到X是O（n）。在最糟糕的情況下，我可以看到它的刪除是O（1）的唯一方式是，如果X本身包含指向鏈接列表中下一個和上一個對象的指針。 – Boon

你的理解是正確的。在最壞的情況下從鏈中刪除O（n）。想象一下，你有一個可怕的哈希函數或桶數量太少。在這種情況下，每次刪除都必須搜索鏈接列表。這是O（n），當然。哈希表刪除僅稱爲O（1），因爲最佳情況和平均情況都需要通過鏈表進行_no_遍歷。 – brycem

散列表操作的成本正在掃描所需密鑰的所選存儲桶的條目。如果密鑰的分佈均勻，則操作的平均成本僅取決於每個桶的平均密鑰數量。換句話說，就負載係數而言。

具有低衝突率和高數量插槽的散列表總是會提供接近O（1）的操作。

即使表格條目數量n比插槽數量高得多，鏈接的散列表仍然有效。它們的性能隨着負載係數的降低更加優雅（線性）。例如，具有1000個插槽和10,000個存儲密鑰（加載因子10）的鏈式哈希表比10,000時隙表（加載因子1）慢五到十倍;但仍然比簡單的順序列表快1000倍。

由此我們說分期付款當假定哈希表有足夠的空間用於負載（AKA的負載因子爲1）時，操作的代價爲O（1）。

來源

2014-11-13 22:19:18 Haney

只是爲了澄清，你是否說存儲在散列表中的項目數量中的存儲桶數量是線性的？（這是您在任何一個存儲桶中只能有O（1）個期望項目的唯一方法。） – chepner

@chepner可能是一個不好的例子，因爲可能的keyspace ==添加的項目數。我會調整它。 – Haney

爲什麼刪除O（1）在你的情況下？
以下內容援引P258的CLRS第三版：

注意雙鏈HASH-DELETE 作爲輸入的元素x，而不是它的密鑰K，這樣我們就不必首先搜索x 。如果散列表支持刪除，則其鏈接列表應該雙重鏈接，以便我們可以快速刪除一個項目。如果列表只是單鏈接的，那麼到刪除元素x，我們首先必須在列表T中找到xx.x：key /，這樣我們就可以更新x的前任的下一個屬性。

我們必須提供要刪除的對象的指針。讓對象是X.那麼，從這個X屬於，我們只是做了以下的雙向鏈表中刪除：

X.left.right = X.right
X.right.left = X .left

完成！刪除是恆定的。上一個下一個指針在X本身，關鍵也是。

來源

2017-04-27 05:26:34 Ciado

如何刪除哈希表中的O（1）雙鏈接鏈接？

回答

相關問題