最壞情況下的搜索次數爲零的散列複雜度

Question

散列表的大小爲11，日期適合位置{3,5,7,9,6}如果未找到數據，必須進行多少次比較在最壞的情況下列表2,11,6

Answer 1

這在很大程度上取決於如何術語的預期和哈希表實現...

• 「11號的哈希表」可能意味着11元素（特別是在C++中，.size()是查找表中有多少元素的函數）或11個桶，但在這種情況下可能意味着後者; 「數據擬合」可能意味着每個桶的位置都有一個數據（單數據），也可能意味着可能有一個或多個（但是如果後者的意圖和「大小「不是桶的數量，沒有答案）。

• 「多少次比較」通常是指鍵-VS-鍵比較，但執行需要執行的桶含量比較反對NO- [更多] - 值哨兵太

• 實現可能處理衝突使用每鬥碰撞密鑰列表，或者它可能老調重彈，或通過從散列到桶

因此，如果我們假設11桶，有些組偏移（位移列表）級聯/跳在每個桶位置只有一個數據項{3,5,7,9,6}和按鍵按鍵比較isons和每個桶名義上的碰撞元素列表，那麼可能發生的最壞情況就是將桶與現有入口進行比較，這意味着按鍵比較，然後是按鍵與哨兵比較。這可以滿足「2」的答案。

如果系統使用位移列表或重新哈希表，通常幾次都不會訪問同一個桶（這在統計上不太可能），所以沒有「最壞情況」的限制，因爲實施放棄了。

如果特定的死簡單的情況下，位移增量嘗試下一個桶，它可能會放棄後訪問一串填充桶並找到第一個空的...給出{3,5,7,9,6}最糟糕的情況是，它比較鍵然後在5和6之間，然後比較7與8的哨兵，進行3或4次總比較，具體取決於你如何計算。

如果大小指示元素的數量，使得11分佈在{3,5,7,9,6}之間，這隻有在任何單獨的桶維護衝突鍵列表時纔可能，則如果這些桶中的4個具有單個鍵，則剩餘的桶可能有11-4 = 7，所以在失敗之前可能有7次按鍵按鍵比較。

很難想象通過任何計數方法對產生6或11次比較的問題的任何合理解釋。

如果有人在學術環境中問過你，在考慮問題時可能會有一些具體的實施和符號約定。如果缺少這樣的上下文，那麼任何人要麼是非常懶惰，要麼不熟悉哈希表的基礎知識。