hashmap刪除複雜性

Question

所以有很多消息來源說hashmap刪除函數是O（1），但我不明白這可能是如何，除非散列表由鏈表返回，因爲列表清除是O（n）。有人可以解釋嗎？

Answer 1

您可以將Hasmap視爲一個數組。想象一下，你想把地球上所有人的物體存儲在地球上。您可以爲每個人獲取唯一的編號，並使用尺寸爲10 * 10^20的數組。 如果某人出生，她/他會獲得下一個免費號碼並被添加到結尾。如果有人死亡，則使用她/他的號碼，數組條目設置爲空。

你可以很容易地看到，添加一些或刪除某人，你只需要恆定的時間。計算陣列地址，完成（如果你有隨機存取存儲器）。

什麼是由Hashmap添加的？有2個動機。一方面，你不想擁有如此龐大的陣列。如果你只想存儲來自世界各地的10個人，幾乎所有的數組條目都是免費的。另一方面，並​​非所有要存儲在某處的數據都有唯一的編號。有時會有多次相同的號碼，有些號碼現在顯示爲整體，有時候您沒有任何號碼。因此，您可以定義一個函數，該函數使用輸入中的大數字並將其減小到較小範圍內的數字。這種減少應該是一種方式，即最終的數字對於不同的輸入來說可能是唯一的。

例如：假設您想要存儲10個數字，從1到100000000.您可以使用一個有100000000個索引的數組。或者你可以使用一個有100個索引的數組，並且函數f（x）= x％100.如果你的數字是1234，那麼f（1234）= 34。

現在你可以問，如果你的號碼是2234，會發生什麼？那麼我們碰撞了。你需要一些策略來處理這個問題，有幾個。研究一些文獻或爲此提出具體問題。

如果你想存儲一個字符串，你可以想象使用每個字符的長度或ascii值的總和。如您所見，我們可以輕鬆存儲某些內容，並輕鬆地再次訪問它。我們必須做什麼？計算函數中的散列（一個好函數的恆定時間），訪問數組（恆定時間），存儲或刪除（恆定時間）。

在現實世界中，一個好的散列函數並不那麼容易。嘗試堅持在Java中包含的。

如果您想了解更多的細節，關於哈希表維基百科的文章是一個很好的起點：http://en.wikipedia.org/wiki/Hash_table

Answer 2

我不認爲刪除（鍵）複雜度爲O（1）。如果我們有一個有很多碰撞的大散列表，那麼在最壞的情況下它就是O（n）。很難得到最壞的情況，但我們不能忽視O（1）不能保證的事實。