c++ - 在微不足道的键的情况下，使用 map 而不是 unordered_map 有什么优势吗？

Question

最近一次关于unordered_mapC++ 的讨论让我意识到，由于查找的效率（amortized O(1) vs. O(log n)unordered_map ），我应该在我以前使用的大多数情况下使用它。大多数时候我使用地图，我使用或者作为键类型；因此，我对哈希函数的定义没有任何问题。我想得越多，我就越意识到在简单类型的键的情况下我找不到任何使用 a over a的理由——我查看了接口，没有找到任何会影响我的代码的重大差异。mapintstd::stringstd::mapstd::unordered_map

因此，问题是：在像and这样的简单类型的情况下，是否有任何真正的理由使用std::mapover ？std::unordered_mapintstd::string

我是从严格的编程角度提出的问题——我知道它没有被完全认为是标准的，而且它可能会给移植带来问题。

另外，我希望正确的答案之一可能是“对于较小的数据集更有效”，因为开销较小（这是真的吗？） - 因此我想将问题限制在密钥是非平凡的（> 1 024）。

编辑： 呃，我忘记了明显的（感谢 GMan！）——是的，地图当然是有序的——我知道，并且正在寻找其他原因。

score 483 · Accepted Answer

不要忘记map保持其元素有序。如果你不能放弃它，显然你不能使用unordered_map.

要记住的另一件事是unordered_map通常会使用更多内存。map只是有一些管家指针和每个对象的内存。相反，unordered_map有一个大数组（在某些实现中可能会变得很大），然后为每个对象增加额外的内存。如果您需要内存感知，map应该证明更好，因为它缺少大数组。

所以，如果你需要纯粹的查找检索，我会说unordered_map这是要走的路。但是总是有取舍的，如果你买不起，那么你就不能使用它。

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

另一方面，我发现重复插入和删除元素要慢得多。这对于相对静态的元素集合来说非常有用，但是如果您要进行大量的插入和删除，那么散列 + 分桶似乎会加起来。（注意，这是经过多次迭代。）

score 145 · Accepted Answer

如果你想比较你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)

score 93 · Accepted Answer

我会回应 GMan 提出的大致相同的观点：根据使用类型，std::map可以（并且通常）比std::tr1::unordered_map（使用 VS 2008 SP1 中包含的实现）更快。

有一些复杂的因素需要牢记。例如，在中std::map，您正在比较键，这意味着您只需要查看足够多的键的开头来区分树的左右子分支。根据我的经验，几乎唯一一次查看整个密钥的情况是，如果您使用的是 int 之类的东西，您可以在一条指令中进行比较。对于像 std::string 这样更典型的键类型，您通常只比较几个字符左右。

相比之下，一个像样的散列函数总是查看整个密钥。IOW，即使表查找的复杂度是恒定的，散列本身也具有大致线性的复杂度（尽管在键的长度上，而不是在项目的数量上）。使用长字符串作为键，anstd::map可能会在 an 开始搜索之前unordered_map完成搜索。

其次，虽然有几种调整哈希表大小的方法，但大多数都非常慢——以至于除非查找比插入和删除频繁得多，否则std::map 通常会比std::unordered_map.

当然，正如我在上一个问题的评论中提到的，您也可以使用树表。这既有优点也有缺点。一方面，它将最坏的情况限制在树上。它还允许快速插入和删除，因为（至少在我完成后）我使用了固定大小的表。消除所有表大小调整可以让您的哈希表更简单，通常更快。

还有一点：散列和基于树的映射的要求是不同的。散列显然需要散列函数和相等比较，其中有序映射需要小于比较。当然，我提到的混合动力车两者都需要。当然，对于使用字符串作为键的常见情况，这并不是真正的问题，但某些类型的键比散列更适合排序（反之亦然）。

score 67 · Accepted Answer

我对@Jerry Coffin 的回答很感兴趣，这表明经过一些实验（可以从pastebin下载），有序映射会在长字符串上表现出性能提升，我发现这似乎只适用于集合对于随机字符串，当使用排序字典（包含具有大量前缀重叠的单词）初始化映射时，此规则会失效，可能是因为检索值所需的树深度增加。结果如下图，第 1 列是插入时间，第 2 列是获取时间。

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

score 39 · Accepted Answer

这里没有真正充分提及的重大差异：

map保持所有元素的迭代器稳定，在 C++17 中，您甚至可以将元素从一个移动map到另一个，而不会使迭代器失效（并且如果在没有任何潜在分配的情况下正确实现）。
map单个操作的时间通常更一致，因为它们从不需要大量分配。
unordered_map如果输入不受信任的输入，在 libstdc++ 中实现的使用std::hash很容易受到 DoS 的攻击（它使用带有恒定种子的 MurmurHash2 - 并不是说播种真的有帮助，请参阅https://emboss.github.io/blog/2012/12/14/破坏杂音哈希泛滥dos重新加载/）。
排序可以实现有效的范围搜索，例如迭代所有 key ≥ 42 的元素。

score 31 · Accepted Answer

我只想指出...有很多种unordered_maps。

在哈希图上查找维基百科文章。根据使用的实现，查找、插入和删除方面的特征可能会有很大差异。

这就是添加到 STL 时最让我担心的问题unordered_map：他们将不得不选择一个特定的实现，因为我怀疑他们会走上这Policy条路，所以我们将被困在一个普通使用的实现上，而没有任何用处其他情况...

例如，一些哈希映射具有线性重新哈希，而不是一次重新哈希整个哈希映射，而是在每次插入时重新哈希一部分，这有助于分摊成本。

另一个例子：一些哈希映射使用简单的节点列表作为存储桶，其他使用映射，其他不使用节点但找到最近的槽，最后一些将使用节点列表但重新排序以便最后访问的元素在前面（就像一个缓存的东西）。

所以目前我倾向于更喜欢std::map或者可能是loki::AssocVector（对于冻结的数据集）。

不要误会我的意思，我想std::unordered_map在未来使用并且我可能会使用，但是当你想到实现它的所有方式以及由此产生的各种性能时，很难“相信”这样一个容器的可移植性这个的。

score 23 · Accepted Answer

概括

假设顺序不重要：

如果您要构建一次大表并进行大量查询，请使用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单独的类型。

表现

下面的两个图表应该不言自明（来源）：

score 20 · Accepted Answer

原因已在其他答案中给出；这是另一个。

std::map（平衡二叉树）操作摊销 O(log n) 和最坏情况 O(log n)。std::unordered_map（哈希表）操作摊销 O(1) 和最坏情况 O(n)。

这在实践中的表现是哈希表每隔一段时间就会“打嗝”一次 O(n) 操作，这可能是您的应用程序可以容忍的，也可能不是。如果它不能容忍它，你会更喜欢 std::map 而不是 std::unordered_map。

score 15 · Accepted Answer

哈希表具有比普通映射实现更高的常量，这对于小型容器来说非常重要。最大尺寸是 10、100，甚至可能是 1,000 或更多？常数和以往一样，但 O(log n) 接近 O(k)。（记住对数复杂度仍然非常好。）

什么是好的散列函数取决于数据的特征；因此，如果我不打算查看自定义哈希函数（但以后肯定会改变主意，而且很容易，因为我在所有东西附近都键入了该死的），即使选择默认值以对许多数据源执行得体，我发现有序map 的性质最初足以提供帮助，在这种情况下，我仍然默认使用 map 而不是哈希表。

另外，您甚至不必考虑为其他（通常是 UDT）类型编写散列函数，只需编写 op< （无论如何您都想要）。

score 10 · Accepted Answer

我最近做了一个测试，可以进行 50000 次合并和排序。这意味着如果字符串键相同，则合并字节字符串。最后的输出应该是排序的。所以这包括对每个插入的查找。

对于map实施，完成这项工作需要 200 毫秒。对于unordered_map+ map，插入需要 70 毫秒，unordered_map插入需要 80 毫秒map。所以混合实现要快 50 毫秒。

我们在使用之前应该三思而后行map。如果您只需要在程序的最终结果中对数据进行排序，那么混合解决方案可能会更好。

score 5 · Accepted Answer

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

整数测试

测试场景包括使用顺序和随机键填充映射，并使用长度在 [17:119] 范围内的字符串值（以 17 的倍数）。使用元素计数在 [10:100000000] 范围内以 10 的幂执行的测试.

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

插入结论：

当映射大小低于 10000 个元素时，在 std::map 中插入扩展键往往优于 std::unordered_map。
在 std::map 中插入密集键不会与 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)

查找结论：

当地图大小低于 1000000 个元素时，搜索传播 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 在许多情况下仍然是更好的选择。作为一个实际的例子，我有一个查找永远不会失败的字典，虽然键的分布很稀疏，但它的执行速度与 std::unordered_map 相同，因为我的元素计数低于 1K。并且内存占用显着降低。

字符串测试

作为参考，我在这里介绍了string[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

内存：64Gb

score 2 · Accepted Answer

以上所有内容的小补充：

更好地使用map，当您需要按范围获取元素时，因为它们已排序并且您可以从一个边界迭代它们到另一个边界。

score 2 · Accepted Answer

如果您使用 Visual Studio 2010 编译项目 - 忘记字符串的 unordered_map。如果您使用更现代的 Studio，例如 2017 - 那么 unordered_map 比有序地图快得多。

score 1 · Accepted Answer

通过使用无序映射，您可以声明代码中没有任何地方依赖被排序的映射。在某些情况下，此附加上下文信息可能有助于了解此映射在程序中的实际使用方式。清晰度可能更重要，因为性能是副作用。

当然，当您需要有序映射时，没有编译器会阻止您使用无序映射，但这不太可能很好地工作，以至于读者可能会认为这不仅仅是一个错误。

score -1 · Accepted Answer

来自：http ://www.cplusplus.com/reference/map/map/

“在内部，地图中的元素始终按照其内部比较对象（比较类型）指示的特定严格弱排序标准按其键排序。

map 容器通常比 unordered_map 容器通过键访问单个元素要慢，但它们允许基于它们的顺序对子集进行直接迭代。”

c++ - 在微不足道的键的情况下，使用 map 而不是 unordered_map 有什么优势吗？

15 回答 15

这里没有真正充分提及的重大差异：

整数测试

一般结论

字符串测试

评估平台

Related

Reference