哈希表的時間複雜度

我對哈希表的時間複雜度感到困惑許多文章都指出它們是「分期付款O（1）」而非真實訂單O（1）這在實際應用中意味着什麼。在哈希表中操作的平均時間複雜度是多少，在實際實現中不是理論上的，爲什麼這些操作不是真實的O（1）？哈希表的時間複雜度

2010-10-16 marme

這是相關的，雖然不是完全一樣的問題：http://stackoverflow.com/ question/2369467/why-are-hash-table-expansions-usually-done-by-doubling-the-size – 2010-10-16 14:34:40

這有助於回答插入，但並未解釋有關其他操作的任何內容，我最感興趣的解釋是在散列表中查找的時間複雜度 – marme 2010-10-16 14:45:21

在散列函數的一些假設下，對於大多數散列表實現來說，查找是真正的O（1）時間。事實上，在有限的桶深度的一些實現中，它在設計上是恆定的。 – 2010-10-16 14:52:31

對於散列表的某些用途，不可能提前創建它們的「正確」大小，因爲不知道在表的生命週期中需要同時保存多少個元素。如果您想保持快速訪問，您需要隨着元素數量的增長不時調整表格大小。調整大小的時間與表中已有元素的數量相關，並且通常在插入時完成，當數字元素通過閾值時。

這些調整大小的操作很少，以至於分攤的插入成本仍然保持不變（通過遵循表格大小的幾何級數，例如每次調整大小時將其大小加倍）。但不時插入一個插入需要O（n）時間，因爲它會觸發調整大小。

實際上，除非您正在構建硬實時應用程序，否則這不是問題。

來源

2010-10-16 14:42:54

這不僅是考慮的尺寸 - 它也是散列碰撞。有不同的方式來處理它們，但無論你做什麼，它都不會在O（1）時間發生。在實踐中，平均情況仍然接近於O（1），儘管除非哈希表得到相當滿。 – Jords 2010-10-16 14:58:14

@Jords我不知道「接近O（1）」是什麼意思。此外，我相當相信文獻中的「攤銷O（1）」對應於哈希函數的假設，其中桶深度保持在固定邊界以下，因此恆定時間。因爲如果沒有調整大小的查找不是恆定的時間，那麼分期查找肯定不是恆定的時間。 – 2010-10-16 15:10:54

事先不可能知道你使用散列函數會得到多少衝突，以及需要調整大小等。這可以添加一個哈希表的性能不可預測的元素，使其不正確O（1）。然而，實際上所有的哈希表實現在廣大，絕大多數的插入中提供了O（1）。這與插入數組相同 - 除非需要調整大小，否則它是O（n），加上碰撞的不確定性。

實際上，散列衝突是非常罕見的，您需要考慮這些細節的唯一條件是您的特定代碼在其必須運行的時間窗口非常緊密時。對於幾乎每個用例，哈希表都是O（1）。比O（1）插入更令人印象深刻的是O（1）查找。

來源

2010-10-16 14:48:08 Puppy

好吧，O（1）查找也是真的數組 – 2016-04-27 19:04:53

上平均情況下插入值劃分爲哈希表需要，，O（1）時間。計算散列函數，從散列表中選擇bucked，然後插入項目。在最壞的情況下，所有的元素將被散列到相同的值，這意味着整個桶列表必須是遍歷的 ，或者在開放尋址的情況下，必須探測整個表格直到一個空的點被發現。因此，在最壞的情況下，插入需要O（n）的時間

參閱：http://www.cs.unc.edu/~plaisted/comp550/Neyer%20paper.pdf（哈希表部分）

來源

2017-04-29 04:08:38

哈希表的時間複雜度

回答

相關問題