c++ - hash_map 和 map 哪个更快？少于 10000 件

Question

vs2005支持::stdext::hash_map::std::map.

然而，在我的测试中，::stdext::hash_map 的插入和删除 OP 似乎比::std::map 慢。(少于 10000 件)

有趣的....

谁能提供一篇关于它们的比较文章？

Answer 1

通常您会查看各种操作的复杂性，这是一个很好的指南:相对于 O(log N) 的插入、查找、删除，hashmap 的分期 O(1) 插入、O(1) 查找、删除基于树的 map 。

但是，在某些情况下，复杂性会产生误导，因为所涉及的常数项非常极端。例如，假设您的 10k 项是键控字符串。进一步假设这些字符串每个都是 100k 个字符长。假设不同的字符串通常在字符串的开头附近不同(例如，如果它们本质上是随机的，则对在第一个字节中不同的概率为 255/256)。

然后要进行查找，散列图必须对 100k 的字符串进行散列。这是集合大小的 O(1)，但可能需要相当长的时间，因为它可能是字符串长度的 O(M)。一棵平衡树必须进行 log N <= 14 次比较，但每次只需要查看几个字节。这可能根本不需要很长时间。

在内存访问方面，使用 64 字节的缓存行大小，hashmap 加载超过 1500 个连续行，并执行 100k 字节的操作，而树加载 15 个随机行(实际上可能是 30 个，因为通过字符串间接访问)并执行 14 *(一些小数字)字节操作。您可以看到前者很可能比后者慢。或者它可能更快:您架构的 FSB 带宽、停顿时间和推测读取缓存有多好？

如果查找找到匹配项，那么当然除了这两个结构之外还需要执行单个全长字符串比较。如果桶中碰巧发生冲突， HashMap 也可能会进行额外的失败比较。

因此假设失败的比较快到可以忽略不计，而成功的比较和散列操作很慢，树的速度可能大约是散列的 1.5-2 倍。如果这些假设不成立，那么它就不会成立。

当然是一个极端的例子，但很容易看出，在您的数据中，特定的 O(log N) 操作可能比特定的 O(1) 操作快得多。你想测试当然是对的，但如果你的测试数据不能代表现实世界，那么你的测试结果也可能不具有代表性。基于复杂性的数据结构比较指的是在 N 接近无穷大时的极限行为。但是 N 不会趋近于无穷大。是 10000。