散列表 - 用於搜索不存在的密鑰的時間複雜度

Question

讓我們有一個帶有n個鍵的散列表，每個鍵都有一個只有一個值的存儲桶。 假設我們尋找一個在哈希表中不存在的關鍵字，那麼這個操作的最壞時間複雜度是什麼？

在我看來，它會是O（n）。散列函數將必須檢查其所有密鑰才能確定給定的密鑰不存在於散列中。

您認爲如何？我對嗎？

Answer 1

這取決於實施。我希望時間複雜度爲O（1），因爲從本質上講，散列表不會遍歷元素來查找元素，而是直接在基於散列方法的內存中索引。超出O（1）的唯一時間是需要重新調整內存大小或遇到衝突時。當然，除此之外還有許多小細節，以及影響事物的散列算法之間的差異。這裏是一個很好的線程來看看以瞭解更多信息：

Hash table runtime complexity (insert, search and delete)