2011-05-04 68 views

回答

9

實際上m應該與n成正比。否則,例如,你可能只有一個桶,它就像一個未分類的集合。更確切地說,如果m與n成比例,即m = c * n,那麼每個桶中的項目數將是n/m = 1/c,這是常數。去任何一個桶是一個O(1)操作(只是計算哈希碼),然後通過桶的搜索是不變的順序(你可以做一個線性搜索桶中的項目,這將是一個常數)。

因此,如果m = c * n,算法的順序是O(1)。

舉一個相反的例子,假設我們有一個固定大小的tableSize大小的表。那麼每個桶中物品的預期數量是n/tableSize,它是n的線性函數。任何一種對桶的搜索最多隻能是一棵樹的O(log(n))(我假設你不會在桶中粘貼另一個散列表,或者我們在散列表上有相同的參數),所以在這種情況下它不會是O(1)。

+0

要添加到此答案,不僅在兩者成比例時,而且當元素數('n')小於或等於桶數('m')時,可以獲得常量訪問時間。否則,我們有'O(1 + | k |)'的情況,其中k是第k個桶中元素的數量。 – 2011-05-04 01:28:56

+1

這仍然是不變的訪問時間。如果k是常數,則O(1 + | k |)= O(1)。 – 2011-05-04 02:18:27

+0

如果我們使用開放尋址來解決衝突,而不是鏈接,那麼幾乎每個哈希表的分析都假設爲?即使m與n成正比,平均常數訪問時間是否仍然保持不變? – sinoTrinity 2014-12-21 17:51:56

0

碰撞的可能性更高,因此必須掃描具有相同散列鍵的項目列表的發生率也更高。

0

訪問時間是恆定的,因爲訪問基於哈希值的計算,然後通過查找來查找合適的存儲桶。假設散列函數在桶之間均勻分配項目,那麼訪問任何單個項目所需的時間將等於訪問其他項目的時間,而不管n是多少。

常量並不一定意味着雖然低。平均訪問時間與散列函數的均勻分佈和桶的數量有關。如果您有數千個物品均勻地分佈在少量的桶中,您可以快速找到桶,然後循環通過桶中的很多物品。如果你有很大比例的桶到項目,但是一個壞的散列函數會把更多的項目放在一些桶中而不是其他桶中,那麼大桶中的項的訪問時間將比其他項的訪問時間慢。

0

合理大小的哈希表,那裏有足夠的插槽,每次存儲和大量的額外的空間元素,將有散列函數做了大部分工作選擇插槽和極少數的碰撞,不同的元素具有相同的哈希。一個非常擁擠的散列表將會有很多衝突,並且會降級到基本的線性搜索,幾乎每個查找都將是一個具有相同散列的錯誤項目,並且您必須繼續搜索正確的項目(散列表查找仍然必須檢查密鑰,一旦它選擇第一個槽,因爲它所查找的密鑰在存儲時可能會發生衝突)。

什麼決定了命中碰撞比是完全數的項的大小-的哈希的比率(即,百分比的機會,一個隨機選擇的時隙將被填充)。

2

嚴格地說,散列表訪問的平均情況時間複雜度實際上是Ω(n 1/3)。信息不能比光速快,這是一個常數。由於空間具有三個維度,存儲數據的n位時,要求一些數據以一定距離位於Ñ1/3的來自CPU的數量級上。

更多詳細信息in my blog