vs2005 支持 ::stdext::hash_map ::std::map。
但是，在我的测试中， ::stdext::hash_map 的插入和删除 OP 似乎比 ::std::map 慢。（少于 10000 项）
有趣的....
任何人都可以提供关于它们的比较文章吗？
问问题
15426 次
6 回答
9
通常你会查看各种操作的复杂性，这是一个很好的指南：amortized O(1) insert、O(1) lookup、delete for a hashmap 而 O(log N) insert、lookup、delete for a tree-基于地图。
然而，在某些情况下，复杂性会产生误导，因为所涉及的常数项是极端的。例如，假设您的 10k 个项目是键控字符串。进一步假设这些字符串的长度均为 100k 个字符。假设不同的字符串通常在字符串开头附近不同（例如，如果它们本质上是随机的，则对在第一个字节中的不同概率为 255/256）。
然后要进行查找，哈希图必须对 100k 字符串进行哈希处理。这是集合大小的 O(1)，但可能需要很长时间，因为它可能是字符串长度的 O(M)。一棵平衡树必须进行 log N <= 14 比较，但每次只需要查看几个字节。这可能根本不需要很长时间。
在内存访问方面，使用 64 字节的缓存行大小，hashmap 加载超过 1500 个连续行，并执行 100k 字节操作，而树加载 15 个随机行（实际上可能是 30 个，由于通过字符串的间接性）并执行 14 *（一些小数字）字节操作。您可以看到前者可能比后者慢。或者它可能更快：您的架构的 FSB 带宽、停顿时间和推测读取缓存有多好？
如果查找找到匹配项，那么当然除此之外，两个结构都需要执行单个全长字符串比较。如果桶中碰巧发生冲突，哈希图可能会进行额外的失败比较。
所以假设失败的比较快到可以忽略不计，而成功的比较和散列操作很慢，那么树的速度可能大约是散列的 1.5-2 倍。如果这些假设不成立，那么就不会成立。
当然，这是一个极端的例子，但很容易看出，在您的数据上，特定的 O(log N) 操作可能比特定的 O(1) 操作快得多。你想测试当然是对的，但是如果你的测试数据不能代表现实世界，那么你的测试结果也可能不具有代表性。基于复杂性的数据结构比较指的是 N 接近无穷大时的极限行为。但是 N 不会接近无穷大。是10000。
于 2009-07-14T11:12:54.227 回答
6
这不仅仅是插入和移除。您必须考虑在 hash_map 与 map 中分配的内存不同，并且您每次都必须计算正在搜索的值的哈希值。
我认为这篇 Dr.Dobbs 文章将最好地回答您的问题：
于 2009-07-14T10:24:53.170 回答
2
这取决于您的使用情况和您的哈希冲突。一个是二叉树，另一个是哈希表。
理想情况下，哈希映射将具有 O(1) 插入和查找，映射 O(ln n)，但它假定非冲突哈希。
于 2009-07-14T10:02:28.567 回答
0
散列表的查找速度应该比二叉树（即 std::map）快。从来没有人建议过它们的插入和删除速度更快。
于 2009-07-14T10:06:37.793 回答
0
哈希映射将创建用于索引的字符串/键的哈希。尽管在证明复杂性时提到了 O(1)，但 hash_map 对每个插入进行冲突检测，因为字符串的哈希可以产生与另一个字符串的哈希相同的索引。因此，哈希映射具有管理这些冲突的复杂性，并且您知道这些冲突是基于输入数据的。
但是，如果您要对结构执行大量查找，请选择 hash_map。
于 2009-07-14T10:09:42.873 回答