如何在map和unordered_map之間進行選擇？

假設我想用字符串作爲關鍵字映射數據。我應該選擇什麼樣的容器，map或unordered_map？ unordered_map佔用更多的內存，所以我們假設內存不是問題，關注的是速度。如何在map和unordered_map之間進行選擇？

unordered_map一般應給予與O（n）的最壞情況下O（1）的平均複雜度。在什麼情況下它會到達O（n）？ map何時比unordered_map獲得更多時間？當n很小時會發生嗎？

假設我會用STL unordered_map與默認haser比。地圖。字符串是關鍵。

如果我要遍歷元素，而不是每次訪問單個元素，我應該更喜歡map？

來源

2012-12-10 StackHeapCollision

您是否需要對映射中的項目進行排序？ –

'unordered_map'的哪個實現使用更多內存？ –

儘管通常可以忽略不計，但在散列映射中始終存在內存開銷。 – ypnos

在實踐中，如果內存是沒有問題，unordered_map總是更快，如果你想單個元素訪問。

最糟糕的情況是理論上的，並且對所有元素的單個散列計數都有約束。這不具有實際意義。只要至少有N個日誌元素屬於同一個散列，unordered_map就會變慢。這也沒有實際意義。在某些特殊情況下，您可以使用特定的哈希算法來確保更均勻的分佈。對於不共享特定模式的普通字符串，與unordered_map一起使用的通用哈希函數一樣好。

如果你想穿越地圖的排序方式（使用迭代器），你不能使用unordered_map。相反，map不僅允許這樣做，還可以基於密鑰的近似值爲您提供映射中的下一個元素（請參閱lower_bound和upper_bound方法）。

來源

2012-12-10 11:07:14 ypnos

這個答案是最好的誤導。「unordered_map對單個元素訪問總是比較快」並不是真的，我唯一能想到的就是它總是更快*分期*和*漸近*。「amortized」是實踐中的一個重要警告：假設它被實現爲某種類型的哈希表，如果我正確記住了我的哈希表，隨着通過插入元素增長它，它會用Ω（n）操作「打嗝」每隔一段時間。這可能是也可能不是任何特定的應用程序可以容忍的。 –

在什麼情況下會得到它的O（N）？

，如果你有其中所有輸入stirngs產生相同的散列值（即產生衝突）這樣的壞哈希函數...

我應該選擇什麼容器，地圖或unordered_map ？

它總是你的要求和種類/數量的問題。

什麼時候地圖比unordered_map更省時？

這只是不同的結構。根據您的典型使用情況，您最好根據自己的典型使用情況選擇其中一種（考慮您擁有的數據類型和數量）

當n很小時，它會發生什麼嗎？

在小數據量的一切的情況下，依賴於特定的STL實現... 所以，有時甚至是一個普通的矢量/陣列可能比關聯容器更快...

來源

2012-12-10 11:07:04 zaufi

我應該選擇什麼容器，map或unordered_map？ unordered_map佔用更多的內存，所以我們假設內存不是問題，而關心的是速度。

配置文件，然後決定。 unordered_map通常速度更快，但每個案例都有所不同。

在什麼情況下它會到達O（n）？

當哈希不好，一堆元素被分配到相同的bin。

什麼時候地圖比unordered_map更省時？當n很小時會感到愉快嗎？

可能不是，但簡介，如果你真的關心。有一個小尺寸的容器是你的程序的瓶頸似乎極不可能。無論如何，對於這種情況，使用線性搜索的簡單vector可能會更快。

決定時，最重要的是訂貨和缺乏迭代器失效的要求。如果你需要，你幾乎不得不使用map。否則，unordered_map。

來源

2012-12-10 11:09:10 Pubby

174

     | map    | unordered_map 
--------------------------------------------------------- 
element ordering  | strict weak  | n/a 
         |     | 
common implementation | balanced tree | hash table 
         | or red-black tree| 
         |     | 
search time   | log(n)   | O(1) if there are no hash collisions 
         |     | Up to O(n) if there are hash collisions 
         |     | O(n) when hash is the same for any key 
         |     |  
Insertion time   | log(n)+rebalance | Same as search 
         |     | 
Deletion time   | log(n)+rebalance | Same as search 
         |     | 
needs comparators  | only operator < | only operator == 
         |     | 
needs hash function | no    | yes 
         |     | 
common use case  | when good hash is| In most other cases. 
         | not possible or | 
         | too slow. Or when| 
         | order is required|

來源

2012-12-10 11:16:33

有關常見實現的評論：紅黑樹是平衡樹（或更具體地說，是一種自平衡二叉搜索樹）的_kind_。 – HelloGoodbye

重新平衡不會超過'log（n）' – mtk

如何在map和unordered_map之間進行選擇？

回答

相關問題