139

现在它std有一个真正的哈希映射unordered_map，为什么（或何时）我仍然想在它实际存在的系统上使用旧map的？unordered_map有没有我无法立即看到的明显情况？

4

5 回答 5

116

如前所述，允许以排序方式遍历元素，但不允许。这在许多情况下都非常重要，例如显示集合（例如地址簿）。这也体现在其他间接方式，如：（1）从返回的迭代器开始迭代，或（2）存在类似的成员函数。mapunordered_mapfind()lower_bound()

另外，我认为最坏情况下的 搜索复杂性存在一些差异。

  • 对于map, 它是 O( lg N )

  • 对于unordered_map，它是 O( N ) [当哈希函数不好导致太多哈希冲突时，可能会发生这种情况。]

这同样适用于最坏情况的 删除复杂性。

于 2010-10-10T23:59:56.070 回答
91

除了上面的答案之外，您还应该注意，仅仅因为unordered_mapis constant speed ( O(1)) 并不意味着它比map(of order log(N)) 快。log(N)由于N受 2 32（或 2 64 ）的限制，该常数可能会更大。

因此，除了其他答案（map维护顺序和散列函数可能很困难）之外，它可能map更具性能。

例如，在我为一篇博客文章运行的程序中，我看到 VS10比 VS10std::unordered_map慢std::map（尽管boost::unordered_map比两者都快）。

性能图

注意第 3 到第 5 个小节。

于 2010-10-11T07:22:03.130 回答
28

这要归功于 Google 的 Chandler Carruth 在他的CppCon 2014 讲座中

std::map（许多人认为）对面向性能的工作没有用：如果您想要 O(1) 分期访问，请使用适当的关联数组（或缺少一个，std::unorderded_map）；如果您想要排序的顺序访问，请使用基于向量的东西。

另外，std::map是一棵平衡树；你必须非常频繁地遍历它，或者重新平衡它。这些分别是缓存杀手和缓存启示录操作……所以对std::map.

您可能对这个关于高效哈希映射实现的SO 问题感兴趣。

（PS -std::unordered_map对缓存不友好，因为它使用链表作为存储桶。）

于 2015-05-10T16:05:36.380 回答
22

我认为很明显，您将使用std::map您需要按排序顺序遍历地图中的项目。

当您更喜欢编写比较运算符（直观）而不是哈希函数（通常非常不直观）时，您也可以使用它。

于 2010-10-10T23:32:06.463 回答
11

假设您有非常大的键，也许是大字符串。要为大字符串创建哈希值，您需要从头到尾遍历整个字符串。密钥的长度至少需要线性时间。但是，当您仅使用键的运算符搜索二叉树时>，每个字符串比较都可以在找到第一个不匹配时返回。对于大字符串来说，这通常很早。

这个推理可以应用于 和的find函数。如果键的性质是生成散列（在 的情况下）比使用二分搜索找到元素的位置（在在. 很容易想到会出现这种情况的场景，但我相信在实践中它们会非常罕见。std::unordered_mapstd::mapstd::unordered_mapstd::mapstd::map

于 2016-08-19T20:22:45.860 回答