在关键字较为简单的情况下，使用map与unordered_map相比有什么优势吗？

Question

在关键字较为简单的情况下，使用map与unordered_map相比有什么优势吗？

529

最近听了有关C++中的unordered_map的讲座后，我意识到大多数情况下应该使用unordered_map而不是map，因为它具有更高效的查找能力（平均O（1）与O(log n)相比）。我使用map的大部分时候，都会使用int或std::string作为键类型；因此，对于哈希函数的定义，我没有什么问题。越想越多，我越来越认识到，在键为简单类型的情况下，我找不到使用std::map而不是std::unordered_map的任何理由--我查看了接口，并没有发现任何影响我的代码的重要区别。

因此，问题来了：在像int和std::string这样的简单类型的情况下，是否有任何真正的理由使用std::map而不是std::unordered_map？

我从纯程序设计角度提出这个问题--我知道它并没有被充分考虑进标准，并且可能在移植时出现问题。

此外，我期望其中一个正确的答案可能是“对于较小的数据集效率更高”，因为有较小的开销（这是真的吗？），因此我想限制问题只针对非微不足道的键数（>1,024）的情况。

编辑：噢，我忘记了显而易见的事情（谢谢GMan！） - 是的，map是有序的--我知道这一点，并且正在寻找其他原因。

- Kornel Kisielewicz

34

我很喜欢在面试中问这个问题：“快速排序什么时候比冒泡排序好？”该问题的答案揭示了复杂性理论的实际应用，而不仅仅是简单的非黑即白的说法，例如O（1）比O（n）好，O（k）等效于O（logn）等。 - Matthieu N.

64

@Beh，我觉得你的意思是“何时冒泡排序比快速排序更好”：P - Kornel Kisielewicz

3

智能指针是否是一个微不足道的关键？ - thomthom

以下是 map 是优势的情况之一：https://stackoverflow.com/questions/51964419/how-to-detect-duplicates-in-a-vector-of-unordered-map - anilbey

4

如果我处在你的位置，我会感到尴尬 :/ 使用这种几乎永远不会有用处并且无端让许多候选人感到尴尬的问题，我认为还不如自己承受尴尬。 - user6547518

4

顺便说一句，回应 @user6547518 的话，这似乎是一个非常愚蠢的面试问题。如果我需要从头实现排序算法，我会考虑我的特定需求/限制，并在实现之前重新查看排序算法的描述。35年前，在互联网和我使用的语言中没有标准实现之前，我可能知道这两者之间的区别，但我不再觉得有必要保留这样的信息。 - cosimo193

15个回答

161

如果您想比较您的 std::map 和 std::unordered_map 实现的速度，您可以使用谷歌的 sparsehash 项目中的 time_hash_map 程序进行测试。例如，在 x86_64 Linux 系统上使用 gcc 4.4.2 编译器。

$ ./time_hash_map
TR1 UNORDERED_MAP (4 byte objects, 10000000 iterations):
map_grow              126.1 ns  (27427396 hashes, 40000000 copies)  290.9 MB
map_predict/grow       67.4 ns  (10000000 hashes, 40000000 copies)  232.8 MB
map_replace            22.3 ns  (37427396 hashes, 40000000 copies)
map_fetch              16.3 ns  (37427396 hashes, 40000000 copies)
map_fetch_empty         9.8 ns  (10000000 hashes,        0 copies)
map_remove             49.1 ns  (37427396 hashes, 40000000 copies)
map_toggle             86.1 ns  (20000000 hashes, 40000000 copies)

STANDARD MAP (4 byte objects, 10000000 iterations):
map_grow              225.3 ns  (       0 hashes, 20000000 copies)  462.4 MB
map_predict/grow      225.1 ns  (       0 hashes, 20000000 copies)  462.6 MB
map_replace           151.2 ns  (       0 hashes, 20000000 copies)
map_fetch             156.0 ns  (       0 hashes, 20000000 copies)
map_fetch_empty         1.4 ns  (       0 hashes,        0 copies)
map_remove            141.0 ns  (       0 hashes, 20000000 copies)
map_toggle             67.3 ns  (       0 hashes, 20000000 copies)

- Blair Zajac

2

似乎无序映射在大多数操作上都比映射更快。即使是插入操作... - Michael IV

7

Sparsehash不再存在，它已被删除或下架。 - User9102d82

2

@User9102d82 我已经编辑了问题，引用了一个waybackmachine链接。 - andreee

17

为了确保其他人也注意到时间以外的数字：这些测试是使用4字节的对象/数据结构（即int）进行的。如果您存储需要更重的哈希或更大的东西（使复制操作更加繁重），标准映射可能很快就会有优势！ - AlexGeorg

98

我同意GMan的看法：根据使用方式不同，std::map 比 std::tr1::unordered_map (使用在VS 2008 SP1中的实现) 更快。

需要注意几个复杂因素。例如，在 std::map 中，你比较的是键，这意味着你只会查看足够来区分树的右侧和左侧子分支的键的开头部分。以我的经验来看，只有当你使用像 int 这样可以用单个指令比较的类型时，才会查看整个键。对于更典型的键类型，如 std::string，通常只会比较几个字符左右。

相比之下，一个合理的哈希函数始终会查看键的全部内容。也就是说，即使表查找是常数复杂度，哈希本身的复杂度大约是线性的（尽管是根据密钥长度而不是项目数量）。对于长字符串作为键的情况，std::map 可能会在 unordered_map 开始搜索之前就完成了搜索。

其次，虽然有几种调整哈希表大小的方法，但它们大多都非常慢 - 除非查找比插入和删除更频繁，否则 std::map 通常比 std::unordered_map 更快。

当然，如我在你之前的问题的评论中提到的那样，你也可以使用一组树的表。这既有优点又有缺点。一方面，它将最坏情况限制为树的情况。它还允许快速插入和删除，因为（至少在我的实现中）我使用了一个固定大小的表。消除所有表调整大小可以使哈希表保持更简单且通常更快速。

还有一点：哈希表和基于树的映射的要求是不同的。哈希需要一个哈希函数和一个相等比较，而有序映射则需要一个小于比较。当然，在我提到的混合方案中两者都需要。当然，对于通常使用字符串作为键的情况，这并不是一个问题，但某些类型的键适合排序而不是哈希（或反之亦然）。

- Jerry Coffin

2

哈希表的大小调整可以通过“动态哈希”技术来减少，该技术包括一个过渡期，在此期间每次插入一个项目时，您还需要重新哈希k个其他项目。当然，在过渡期间，这意味着您必须搜索2个不同的表... - Matthieu M.

4

如果键值较长，当在集合中查找不含有该键值时，std::map可能在unordered_map开始查找之前就完成了查找。如果键值存在于集合中，则需要完全比较以确认匹配。但是同样地，unordered_map也需要通过完全比较来确认散列匹配，因此这完全取决于您所比较的查找过程的哪些部分。 - Steve Jessop

2

通常情况下，您可以根据数据的特点替换哈希函数。例如，如果您的长字符串在最后20个字节中的变化比前100个字节更大，则只需哈希最后20个字节即可。 - Erik Aronesty

70

我对@Jerry Coffin的答案很感兴趣，他建议使用有序映射在长字符串上会表现出更好的性能。经过一些实验（可以从pastebin下载），我发现这只对随机字符串集合成立，当有序字典（其中包含具有相当数量前缀重叠的单词）初始化映射时，这个规则就不再适用，可能是由于需要检索值而导致树深度增加。下面显示了结果，第一列是插入时间，第二列是获取时间。

g++ -g -O3 --std=c++0x   -c -o stdtests.o stdtests.cpp
g++ -o stdtests stdtests.o
gmurphy@interloper:HashTests$ ./stdtests
# 1st number column is insert time, 2nd is fetch time
 ** Integer Keys ** 
 unordered:      137      15
   ordered:      168      81
 ** Random String Keys ** 
 unordered:       55      50
   ordered:       33      31
 ** Real Words Keys ** 
 unordered:      278      76
   ordered:      516     298

- Gearoid Murphy

5

感谢进行测试。为了确保我们不测量到噪音，我修改了测试使每个操作运行多次（并将计数器插入映射表中）。我在不同数量的键（从2到1000）和最多约100个键的情况下运行测试，结果表明对于整数键，std::map 通常优于 std::unordered_map，但在约100个键左右时，std::map 失去优势，std::unordered_map 开始胜出。如果将一个已经排序好的序列插入 std::map 中，则效率非常低，你会得到最坏的情况（O(N)）。 - Andreas Magnusson

45

这里有一些显著的区别还没有被充分提到：

map 保持对所有元素的迭代器稳定，而且在C++17中，甚至可以将元素从一个map移动到另一个map而不会使迭代器失效（如果正确实现则不会发生任何潜在的内存分配）。
map 单个操作的计时通常更加一致，因为它们从来不需要进行大容量的内存分配。
unordered_map 使用libstdc++中实现的std::hash容易受到DoS攻击，如果给它不受信任的输入（它使用具有恒定种子的MurmurHash2算法——尽管使用种子也无助于解决问题，详见https://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/）。
有序使得高效的范围搜索成为可能，例如遍历所有键大于等于42的元素。

- user1531083

32

概述

假设顺序不重要：

如果您要构建一次大表并执行大量查询，请使用std::unordered_map
如果您要构建小表（可能少于100个元素）并执行大量查询，请使用std::map。这是因为它的读取是O(log n)。
如果您要频繁更改表格，则可能 std::map 是一个好选择。
如果您有疑问，只需使用std::unordered_map。

历史背景

在大多数语言中，无序映射（也称哈希基础字典）是默认映射，但在C++中，有序映射是默认映射。这是怎么发生的？一些人错误地认为C++委员会在他们独特的智慧中做出了这个决定，但事实比这更丑陋。

广泛认为，C++默认使用有序映射是因为对于它们的实现没有太多的参数。另一方面，基于哈希的实现有很多要讨论的事情。因此，为了避免在标准化中发生僵局，他们只好使用有序映射。大约在2005年，许多语言已经有了良好的基于哈希的实现，因此委员会更容易接受新的std::unordered_map。在完美的世界里，std::map应该是无序的，我们应该有std::ordered_map作为单独的类型。

性能

下面两张图应该可以说明问题(来源)：

- Shital Shah

有趣的数据；你在测试中包含了多少个平台？ - Toby Speight

3

根据您发布的两张图片，std::unordered_map 总是比 std::map 执行得更好，那么在进行大量查询时为什么我应该使用 std::map 而不是 std::unordered_map 呢？ - ricky

图表显示了0.13M或更多元素的性能。如果您只有少量（可能小于100）元素，则O(log n)可能会比无序映射更小。 - Shital Shah

31

我只想指出...有许多种无序映射。请查看哈希表的Wikipedia Article。根据使用的具体实现，查找、插入和删除的特性可能会有很大不同。这就是我对STL添加unordered_map最担心的地方：他们将不得不选择一种特定的实现，因为我怀疑他们不会采用Policy方法，所以我们将被困在一个适用于平均使用的实现中，而其他情况则没有任何东西可用......例如，一些哈希映射具有线性重新哈希，其中不是一次重新哈希整个哈希映射，而是在每次插入时重新哈希一部分，这有助于分摊成本。另一个例子：一些哈希映射使用节点列表作为桶，其他使用映射，其他不使用节点但找到最近的插槽，最后一些将使用节点列表，但重新排序，以便最后访问的元素位于前面（像缓存一样）。因此，目前我倾向于使用std::map或者可能是loki::AssocVector（对于冻结数据集）。别误解我的意思，我想使用std::unordered_map，也许将来会使用，但当你考虑到所有实现方式和各种性能时，很难“信任”这种容器的可移植性。

- Matthieu M.

22

+1：有道理，使用自己的实现时生活更轻松——至少我知道它哪里不好：> - Kornel Kisielewicz

28

我认为这个问题部分得到了回答，因为没有提供有关使用“int”类型作为键的性能信息。我进行了自己的分析，并发现当使用整数作为键时，在许多实际情况下，std::map可以比std::unordered_map更快地执行（速度更快）。

整数测试

测试场景包括使用连续和随机键以及字符串值填充映射，字符串长度在[17:119]范围内且为17的倍数。测试是在元素数量[10:100000000]的幂级别下进行的。

Labels:

Map64: std::map<uint64_t,std::string>
Map32: std::map<uint32_t,std::string>
uMap64: std::unordered_map<uint64_t,std::string>
uMap32: std::unordered_map<uint32_t,std::string>

插入

Labels:

Sequencial Key Insert: maps were constructed with keys in the range [0-ElementCount]
Random Key Insert: maps were constructed with random keys in the full range of the type

插入操作的结论：

在std::map中插入分散的键（spread keys），当地图大小小于10000个元素时，性能优于std::unordered_map。
在std::map中插入密集的键（dense keys），当地图大小小于1000个元素时，与std::unordered_map没有性能差异。
在所有其他情况下，std::unordered_map倾向于表现更快。

查找

Labels:

Sequential Key - Seq. Search: Search is performed in the dense map (keys are sequential). All searched keys exists in the map.
Random Key - Rand. Search: Search is performed in the sparse map (keys are random). All searched keys exists in the map.

(label names can be miss leading, sorry about that)

关于“查找”的结论：

当映射大小在100万个元素以下时，搜索 std::map 的性能略优于 std::unordered_map。
在密集的 std::map 上搜索优于 std::unordered_map。

查找失败

Labels:

Sequential Key - Rand. Search: Search is performed in the dense map. Most keys do not exists in the map.
Random Key - Seq. Search: Search is performed in the sparse map. Most keys do not exists in the map.

(label names can be miss leading, sorry about that)

失败查询结论：

std::map 中的搜索未命中会有很大影响。

总体结论

即使需要速度，对于整数键，std::map 在许多情况下仍然是更好的选择。作为一个实际例子，我有一个字典，查询从不失败，尽管键具有稀疏分布，在元素计数低于 1K 的情况下，它的性能将不会比 std::unordered_map 差，并且内存占用显著更低。

字符串测试

为了参考，这里介绍 字符串[string] 映射的时间。键字符串由随机 uint64_t 值形成，值字符串与其他测试中使用的相同。

Labels:

MapString: std::map<std::string,std::string>
uMapString: std::unordered_map<std::string,std::string>

评估平台

操作系统：Linux - OpenSuse Tumbleweed

编译器：g++（SUSE Linux）11.2.1 20210816

CPU：Intel（R）Core（TM）i9-9900 CPU @ 3.10GHz

RAM：64Gb

- Pablo Yaggi

1

低地图尺寸（小于10）的性能也是相关的。 - yugr

1

为什么这个答案的投票数这么低？（我认为它应该比问题本身有更多的投票，因为它用最简单和最强大的方式回答了其他非常相关的问题） - Matias Haeussler

22

其他答案已经提供了原因；这里再给出一个。

std::map（平衡二叉树）操作的摊销复杂度为O（log n），最坏复杂度为O（log n）。 std::unordered_map（哈希表）操作的摊销复杂度是O（1），最坏复杂度是O（n）。

在实践中，哈希表会间歇性地出现O（n）操作，这可能是您的应用程序可以或不可以容忍的内容。如果不能容忍，则更喜欢使用std :: map而不是std :: unordered_map。

- Don Hatch

15

哈希表相对于普通的映射实现具有更高的常数，这在小容器中变得非常重要。最大大小是10、100，甚至可能是1,000或更多？常数与以往相同，但O(log n)接近于O(k)。（请记住，对数复杂度仍然非常好）。

一个好的哈希函数取决于您数据的特性；因此，如果我不打算查看自定义哈希函数（但我肯定可以改变主意，而且很容易，因为我几乎会为所有内容定义typedef），即使默认值被选择为在许多数据源上表现良好，我发现映射的有序性质对于初始阶段提供了足够的帮助，所以在这种情况下我仍然默认使用映射而不是哈希表。

此外，这样你甚至不用考虑编写其他（通常是UDT）类型的哈希函数，只需编写op<（无论如何，你都想要）。

- Roger Pate

@Roger，你知道unordered_map比map表现更好的元素数量大约是多少吗？不过我可能会写一个测试来验证一下... (+1) - Kornel Kisielewicz

1

@Kornel：不需要太多；我的测试大约有10,000个元素。如果我们想要一个真正准确的图表，你可以查看map和unordered_map的实现，结合特定平台和缓存大小，进行复杂分析。 :P - GManNickG

取决于实现细节、编译时调优参数（如果您正在编写自己的实现，则易于支持）甚至用于测试的特定机器。就像对于其他容器一样，委员会只设置广泛的要求。 - Roger Pate

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- GManNickG · Accepted Answer

不要忘记，map 保持元素的有序性。如果你不能放弃这一点，那么显然你就不能使用 unordered_map。

还需要注意的是，unordered_map 通常使用更多的内存。 map 只有一些维护指针和每个对象的内存。相反，unordered_map 有一个大数组（在某些实现中可能很大），然后为每个对象添加额外的内存。如果你需要关注内存， map 应该会更好，因为它没有大数组。

所以，如果你需要纯查找检索，我建议使用unordered_map。但总是有权衡取舍的，如果你负担不起它们，那么你就不能使用它。

仅从个人经验而言，在主实体查找表中使用 unordered_map 而不是 map ，我发现性能有了巨大的改进（当然是经过测量的）。

另一方面，我发现在重复插入和删除元素时速度要慢得多。对于相对静态的元素集合非常好，但如果你正在进行大量插入和删除操作，则哈希+分桶似乎会累加。（注意，这是经过多次迭代得出的结论。）