哈希表運行時複雜性（插入，搜索和刪除）

爲什麼我在哈希表上看到這些函數的不同運行時複雜性？哈希表運行時複雜性（插入，搜索和刪除）

在維基上，搜索和刪除是O（n）（我認爲散列表的要點是有恆定的查找，所以如果搜索是O（n），有什麼意義）。

在某些課程筆記中，我發現很多複雜性取決於某些細節，包括所有O（1）。如果我能得到所有的O（1），爲什麼還要使用其他實現？

如果我在像C++或Java這樣的語言中使用標準哈希表，我可以期望時間複雜度是多少？

來源

2012-02-09 user1136342

完美已經是O（1）查找，但是你要知道，當你設計表中的數據將是什麼。 – 2012-02-09 16:15:13

O（n）是最壞的情況，O（1）是平均情況。在最糟糕的情況下，您可能會將N個元素全部插入同一個存儲桶中。那麼，對於這個數據集，刪除和搜索也將是O（n）。 – 2012-02-09 16:25:04

相關：[「哈希表的時間複雜度」]（http://stackoverflow.com/questions/3949217/time-complexity-of-hash-table） – 2015-05-24 13:32:44

Hash tables是O(1)平均amortized情況的複雜性，但它從O(n)最壞的情況下時間複雜度受到影響。[我想這就是你的困惑是]

哈希表遭受O(n)最壞的時間複雜度是由於兩個原因：

如果有太多的元素被散列到相同的密鑰：看這關鍵內部可能採取O(n)時間。
一旦散列表已通過其load balance - 它必須重新哈希[創建一個新的更大的表，並重新插入每個元素到表]。

但是，它被認爲是O(1)平均攤銷情況，因爲：

這是非常罕見的，許多項目將被散列到同一個鍵[如果你選擇了一個好的哈希函數，你沒有太大的負載平衡。
的翻版操作，這是O(n)，最多可後n/2 OPS發生，這都是假設O(1)：因此，當你總結每個操作的平均時間，你會得到：(n*O(1) + O(n))/n) = O(1)

注意，因爲換湯不換藥的問題 - 實時應用程序和需要低的應用程序latency - 不應該使用散列表作爲其數據結構。

編輯：用哈希表 Annother問題：cache
另一個問題，你可能會看到大量的哈希表性能損失是由於緩存性能。 哈希表受到緩存性能不佳的影響，因此對於大型收集 - 訪問時間可能需要更長的時間，因爲您需要將表中的相關部分從內存重新加載回緩存。

來源

2012-02-09 16:17:39 amit

謝謝，我想我明白了。因此，如果在考試或面試時詢問我是否提供了一個在O（1）中執行查找的數據結構，那麼您是否知道是否包含哈希表會很好？ – user1136342 2012-02-09 16:24:49

@ user1136342：這取決於您是否需要最差情況或平均情況。對於一般情況，散列表是'O（1）'。如果你需要最壞的情況 - 散列表將是不夠的。 – amit 2012-02-09 16:29:24

取決於你如何實現散列，最糟糕的情況下可以去O（n），最好是0（1）（如果你的DS不容易那麼大，你可以實現）

來源

2012-02-09 16:06:47

爲什麼要實現它，以便它是O（n）如果你可以實現它使其成爲O（1）？ – user1136342 2012-02-09 16:08:09

以及我在最壞的情況下說過 – 2012-02-09 16:13:54

@JigarJoshi：你能否在最壞的情況下獲得O（n）運行時間的例子？ – Rachel 2012-02-09 20:41:34

也許你在看空間的複雜性？那是O（n）。其他複雜性與hash table條目中的預期相同。隨着桶的數量增加，搜索複雜性接近O（1）。如果在最壞的情況下，散列表中只有一個桶，那麼搜索複雜度爲O（n）。

編輯在迴應評論我不認爲這是正確的說O（1）是平均情況。它確實是（如維基百科頁面所述）O（1 + n/k）其中K是哈希表大小。如果K足夠大，那麼結果就是O（1）。但假設K是10，N是100.在這種情況下，每個桶平均有10個入口，所以搜索時間肯定不是O（1）;它是通過多達10個條目的線性搜索。

來源

2012-02-09 16:08:07

哦，我只是看最壞的情況。所以要清楚，當人們說O（1）他們只是意味着平均情況？ – user1136342 2012-02-09 16:13:50

@ user1136342：編輯答案試圖澄清這一點。 – 2012-02-09 16:22:26

散列表的[load balance]（http://en.wikipedia.org/wiki/Load_balancing_%28computing%29）是'table_size/8 <= #elements <= table_size/2'，所以它回到'O（1）'。但是，如果表的大小是動態的 - 仍然存在重新調整問題，這也是最糟糕的情況，即O（n）。查看我的答案以獲得詳細信息和解釋。 – amit 2012-02-09 16:28:06

理想情況下，散列表是O(1)。問題是如果兩個鍵不相等，但它們會導致相同的散列。

例如，假設字符串「這是最好的時代也是最壞的時代」和「綠雞蛋和火腿」都導致了123的哈希值。

當插入第一個字符串時，它將放入存儲區123.插入第二個字符串時，將看到存儲區123的值已存在。然後，它會將新值與現有值進行比較，並看到它們不相等。在這種情況下，將爲該密鑰創建一個數組或鏈接列表。此時，檢索此值變爲O(n)，因爲散列表需要遍歷該存儲桶中的每個值以找到所需值。

因此，使用哈希表時，使用具有非常好的哈希函數的密鑰非常重要，該哈希函數既快又不常導致不同對象的重複值。

有意義嗎？

來源

2012-02-09 16:10:03

一些哈希表（杜鵑散列）保證了O（1）查找

來源

2014-03-19 01:03:17 Demi

哈希表運行時複雜性（插入，搜索和刪除）

回答

相關問題