如何在map和unordered_map之间选择？

Question

假设我想用字符串作为键来映射数据。应该选择哪个容器，map 还是 unordered_map？假设内存不是问题，关注的是速度，unordered_map 通常会给出平均复杂度 O(1)，最坏情况下为 O(n)。 什么情况下会达到 O(n)？在什么情况下 map 比 unordered_map 更高效？当 n 很小的时候发生吗？假设我要使用 STL unordered_map，默认哈希函数，字符串是键。如果我要迭代元素而不是每次访问单个元素，我应该选择 map 吗？

- StackHeapCollision

---

需要将映射中的项目排序吗？ - Some programmer dude

哪个unordered_map的实现使用更多的内存？ - Peter Wood

虽然哈希映射的内存开销通常可以忽略不计，但你总是需要一定的内存开销。 - ypnos

这只是一个小问题，但是既然你提到了迭代，值得指出的是，如果你在插入元素时进行迭代，应该优先选择 map 而不是 unordered_map。 - John McFarlane

可能是在使用平凡键的情况下，使用map是否比unordered_map更有优势？的重复问题。 - phuclv

Answer 1

                       | 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| 

- user1773602

---

关于常见实现的评论：红黑树是一种平衡树（更具体地说，是一种自平衡的二叉搜索树）。 - HelloGoodbye

重新平衡将不会超过log(n)的时间。 - mtk

遍历所有元素怎么样？ - Shashwat

为什么 map 的元素排序是“严格弱”？ - John

@user1773602，我们可以知道这张桌子是在哪里找到的吗？还是说是您自己制作的？ - undefined

Answer 2

实际应用中，如果内存不是问题，unordered_map在单个元素访问方面总是更快的。

最坏情况是理论上的，限制于一个哈希值包含所有元素。这对实际无关紧要。只要你有至少对数 N 个属于同一哈希值的元素，unordered_map 就会变慢。这也对实际无关紧要。在某些特殊场景下，您可以使用特定的哈希算法，以确保更加均匀的分布。对于不共享特定模式的普通字符串，与 unordered_map 一起提供的通用哈希函数同样好。

如果您想以排序方式遍历（使用迭代器）映射，就不能使用 unordered_map。相反，map 不仅允许这样做，而且还可以根据键的近似值为您提供地图中的下一个元素（请参见 lower_bound 和 upper_bound 方法）。

- ypnos

---

这个答案至少是误导性的。"unordered_map 在单元素访问时总是更快"的说法并不正确，唯一我能想到的总是正确的是它在摊销和渐进意义下总是更快。"摊销"在实践中是一个重要的限制条件：假设它被实现为某种哈希表，如果我记得我的哈希表正确的话，随着插入元素的增加，它将会每隔一段时间出现一个Ω(n)的操作，这可能是任何特定应用程序可以容忍的东西也可能不是。 - Don Hatch

使用了有趣的“实践中”这个术语。假设我们编写时间关键系统，例如火箭发动机控制器、金融交易系统或心脏起搏器控制器。我们需要一张地图。在99.999%的情况下，std::map比std::unordered_map慢，仅仅因为std::unordered_map平均复杂度是O(1)。但在0.001%的情况下，我们将得到最坏的情况，即std::unordered_map的复杂度将是O(n)。所以我们会发生什么？火箭失事、损失数百万、人员死亡。也许不是每天，甚至可能不是每年都会发生。但最坏的情况确实会发生。而std::map具有最坏情况O(log n)的复杂度可以处理它们，而unordered_map则无法处理。 - Ezh

如果你写一个火箭发动机控制器，希望你不需要去在Stack Overflow上问关于数据结构和算法的基础知识。这是每个大学计算机科学本科课程广泛讲授的主题，比这里提出的问题深入得多。 - ypnos

Answer 3

在什么情况下会变成O(n)？

如果您有一个糟糕的哈希函数，该函数为所有输入字符串生成相同的哈希值（即产生冲突）...

我应该选择哪个容器，map还是unordered_map？

这始终是要考虑需求和数据种类/数量的问题。

什么时候使用map比unordered_map更有效率？

它们只是不同的结构。最好根据典型的使用情况（考虑您拥有的数据类型及其数量）选择使用其中之一。

n很小时会发生吗？

在小数据量的情况下，一切都取决于特定的STL实现...因此有时甚至普通的向量/数组比关联容器更快...

- zaufi

Answer 4

我应该选择哪种容器，map 还是 unordered_map？假设内存不是问题，关注的是速度。

进行性能分析后再决定。一般情况下，unordered_map 更快，但具体情况因人而异。

在什么情况下会变成 O(n)？

当哈希函数不好，很多元素被分配到同一个桶中时。

何时 map 比 unordered_map 更高效？当 n 很小时，是否会发生？

可能不会，但如果你真的关心的话，可以进行性能分析。让容器大小成为程序瓶颈似乎极不可能。无论如何，在这种情况下，使用线性搜索的简单 vector 可能更快。

最重要的决定因素是排序和迭代器失效的要求。如果需要其中之一，必须使用 map。否则，使用 unordered_map。

- Pubby

Answer 5

std::map内部使用平衡二叉搜索树存储元素。因此，元素将按键的排序顺序存储。

std::unordered_map使用哈希表存储元素。因此，元素不会按任何排序顺序存储。它们将以任意顺序存储。

内存使用：

与map相比，unordered_map的内存使用更多，因为unordered_map需要空间来存储哈希表。

搜索元素的时间复杂度：

在std::map中搜索元素的时间复杂度为O(log n)。即使在最坏情况下，它也将是O(log n)，因为元素在内部存储为平衡二叉搜索树（BST）。

而在std::unordered_map中，搜索的最佳情况时间复杂度为O(1)。但是，如果哈希码函数不好，则最坏情况的复杂度可能为O(n)。

- Shahid Hussain