在普通键的情况下使用map over unordered_map有什么好处吗？

Question

最近unordered_map在C++中的讨论使我意识到,我应该使用之前使用unordered_map过的大多数情况map,因为查找的效率(摊销的O(1)与O(log n)).大多数时候我使用的地图我使用int或std::string作为键,因此我对哈希函数的定义没有任何问题.我越是想到它,我就越发现我发现std::map在一个简单类型的情况下我找不到任何理由std::unordered_map- 我看了一下界面,并没有发现任何显着的差异会影响我的代码.

因此,这个问题-有没有使用任何真正的原因std::map在std::unordered map简单类型一样的情况下,int和std::string？

我从一个严格的编程角度问我 - 我知道它没有被完全认为是标准的,并且它可能会带来移植问题.

另外我希望正确的答案之一可能是"它对于较小的数据集更有效",因为开销较小(是真的吗？) - 因此我想将问题限制在密钥数量的情况下是非平凡的(> 1 024).

编辑: 呃,我忘记了显而易见的(感谢GMan!) - 是的,地图是当然有序的 - 我知道,我正在寻找其他原因.

Answer 1

不要忘记map保持他们的元素有序.如果你不能放弃,显然你不能使用unordered_map.

要记住的其他事情unordered_map通常是使用更多的内存.一个map只对每个对象的几个看家指针,则内存.相反,它unordered_map有一个大数组(在某些实现中可能会变得很大),然后为每个对象增加内存.如果你需要内存感知,map应该证明更好,因为它缺少大数组.

所以,如果你需要纯粹的查找检索,我会说unordered_map是一种方法.但总有权衡,如果你负担不起,那么你就不能使用它.

仅从个人经验来看unordered_map,当map在主实体查找表中使用而不是a 时,我发现性能(当然是衡量的)有了巨大的改进.

另一方面,我发现重复插入和删除元素要慢得多.这对于一个相对静态的元素集合来说非常棒,但是如果你进行了大量的插入和删除操作,那么散列+分组似乎就会增加.(注意,这是经过多次迭代.)

Answer 2

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

Answer 3

我回应了GMan所做的大致相同的观点:取决于使用的类型,std::map可以(并且经常)比std::tr1::unordered_map(使用VS 2008 SP1中包含的实现)更快.

要记住一些复杂因素.例如,std::map你在比较键,这意味着你只要看一下键的开头就足以区分树的右边和左边的子分支.根据我的经验,几乎每次查看整个键都是因为你使用的是int,你可以在一条指令中进行比较.使用更典型的密钥类型(如std :: string),您通常只会比较几个字符左右.

相比之下,一个体面的哈希函数总是会查看整个键.IOW,即使表查找是恒定的复杂性,散列本身也具有大致线性的复杂性(尽管在键的长度上,而不是项的数量).使用长字符串作为键,std::map可能会在unordered_map甚至开始搜索之前完成搜索.

其次,虽然有调整哈希表的几种方法,其中大部分是相当缓慢的-到如此地步,除非查找是大大高于插入和缺失,更频繁的std ::地图通常会比快std::unordered_map.

当然,正如我在上一个问题的评论中所提到的,您也可以使用树木表格.这有利有弊.一方面,它将最坏的情况限制为树的情况.它还允许快速插入和删除,因为(至少在我完成它时)我使用了固定大小的表.消除所有表调整大小可以使您的哈希表更加简单,通常更快.

另一点:散列和基于树的地图的要求是不同的.散列显然需要散列函数和相等比较,其中有序映射需要小于比较.当然,我提到的混合动力需要两者.当然,对于使用字符串作为键的常见情况,这不是一个真正的问题,但某些类型的键比散列更适合排序(反之亦然).

Answer 4

我对@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

Answer 5

我只想指出......有很多种unordered_map.

在哈希映射上查找维基百科文章.根据使用的实施方式,查找,插入和删除方面的特征可能会有很大差异.

而这正是我担心的最有加入unordered_map到STL:他们将不得不选择一个特定的实现,我怀疑他们会往下走的Policy道路,所以我们将用已平均使用并没有为实现被卡住其他情况......

例如,一些散列映射具有线性重新散列,其中不是一次重新散列整个散列映射,而是在每次插入时重新散列一部分,这有助于分摊成本.

另一个例子:一些哈希映射使用一个简单的节点列表用于存储桶,其他使用一个映射,另一些不使用节点但找到最近的插槽,最后一些将使用节点列表但重新排序以便最后访问的元素在前面(就像一个缓存的东西).

所以目前我倾向于选择std::map或者更喜欢loki::AssocVector(对于冻结的数据集).

不要误会我的意思,我希望std::unordered_map将来可以使用,但是当你想到实现它的所有方法以及导致的各种性能时,很难"信任"这种容器的可移植性.这个的.

Answer 6

我认为这个问题得到了部分回答，因为没有提供有关“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

Answer 7

这里没有充分提到的重大差异:

• map保持所有元素的迭代器稳定,在C++ 17中,您甚至可以将元素从一个元素移动map到另一个元素而不会使对它们的迭代器失效(如果在没有任何潜在分配的情况下正确实现).
• map 单个操作的计时通常更一致,因为它们从不需要大量分配.
• unordered_mapstd::hash如果使用不受信任的输入,那么使用libstdc ++中实现的使用很容易受到DoS的影响(它使用具有常量种子的MurmurHash2 - 而不是播种真的会有帮助,请参阅https://emboss.github.io/blog/2012/12/14/ break-murmur-hash-flooding-dos-reloaded /).
• 被排序可以实现有效的范围搜索,例如,使用key> = 42迭代所有元素.

Answer 8

散列表具有比常见映射实现更高的常量,这对于小容器来说变得很重要.最大尺寸是10,100,甚至可能是1,000或更多？常量与以前相同,但O(log n)接近O(k).(记住对数复杂性仍然非常好.)

良好散列函数的作用取决于数据的特征; 因此,如果我不打算查看自定义哈希函数(但后来肯定会改变我的想法,而且很容易因为我在所有内容附近输入),即使默认选择对许多数据源执行得体,我发现有序地图的本质是足够的帮助最初我仍然默认映射而不是在这种情况下的哈希表.

另外,您甚至不必考虑为其他(通常是UDT)类型编写哈希函数,只需编写op <(无论如何你想要).

Answer 9

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

std :: map(平衡二叉树)操作分摊为O(log n),最差情况为O(log n).std :: unordered_map(哈希表)操作分摊为O(1),最差情况为O(n).

这在实践中如何发挥作用是哈希表每隔一段时间用一次O(n)操作"打嗝",这可能是你的应用程序可以容忍的东西,也可能不是.如果它不能容忍它,你更喜欢std :: map over std :: unordered_map.

Answer 10

我最近做了一个测试,使50000合并和排序.这意味着如果字符串键相同,则合并字节字符串.并且应该对最终输出进行排序.所以这包括查找每个插入.

对于map实现,完成作业需要200毫秒.对于unordered_map+ map,unordered_map插入需要70 ms,插入需要80 ms map.因此混合实现速度提高了50毫秒.

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

Answer 11

摘要

假设排序并不重要：

• 如果您要一次构建大表并进行大量查询，请使用 std::unordered_map
• 如果您要构建小表（可能少于100个元素）并进行大量查询，请使用std::map。这是因为对其进行读取O(log n)。
• 如果您打算大量更换桌子，那么可能 std::map是个不错的选择。
• 如有疑问，请使用std::unordered_map。

历史背景

在大多数语言中，无序映射（也称为基于哈希的字典）是默认映射，但是在C ++中，您将有序映射作为默认映射。那是怎么发生的？有人错误地认为C ++委员会以其独特的智慧做出了这一决定，但不幸的是，事实比这更丑。

人们普遍认为，C ++最终将默认的有序映射表作为对象，因为关于如何实现它们没有太多参数。另一方面，基于哈希的实现还有很多事情要谈。因此，为了避免标准化中的僵局，他们只是与有序地图相处。在2005年左右，许多语言已经有了基于散列的实现的良好实现，因此委员会接受new更加容易std::unordered_map。在一个完美的世界中，std::map本来应该是无序的，而我们将std::ordered_map成为单独的类型。

性能

以下两个图表应能说明问题（来源）：

Answer 12

对上述所有内容的小补充：

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