又一个关于有序映射和无序（哈希）映射的问题

Question

又一个关于有序映射和无序（哈希）映射的问题

3

这是一个非常朴素的问题，但我找不到明确的讨论。大家都同意，对于只有10个元素的映射容器来说，使用哈希是过度杀伤。使用有序映射会更快。对于一百个、一千个等等，映射应该按照logN（N=映射中键值对的数量）扩展。所以对于一千个，需要三倍的时间；一百万个，需要六倍的时间；一百亿个，需要九倍的时间。

当然，我们相信，对于精心设计的哈希容器，可以在O(1)（常数）的时间内搜索，而排序容器需要O(logN)的时间。但隐含的常数是多少？哈希映射何时会被排序映射超越？特别是，如果键是整数，则键搜索的开销很小，因此映射中的常数将很小。

尽管如此，几乎所有人都认为哈希容器更快。进行了许多实时测试。

这是怎么回事？

- Mike Razar

糟糕，十倍长了……不过这并没有太大的区别。 - Mike Razar

6

你使用的日志不对，对于基于二叉树的映射应该使用基数为2而不是10。 - Chris Dodd

3个回答

1

正如你所指出的那样 - 魔鬼就在细节中（在这种情况下，是常量）。您必须对您的代码进行基准测试，以决定哪个更高效，因为 O-Notation 是用于无穷小值，而你正在处理真实世界的限制。

如果哈希确实是 O(1)（即哈希函数确实非常好），并且哈希函数计算相对较快（首先不取决于输入大小），则哈希将更快。

在映射上的开销是遍历树，虽然键比较可能更快或更慢（整数更快，字符串更慢），但遍历树始终取决于输入（树深度）。对于较大的树，请考虑使用 B-Tree 而不是标准映射（在 C++ 中通常使用红黑树实现）。

再次强调，关键词是 基准测试。

- littleadv

1

哈希表更快的确切点将取决于机器。

遍历哈希表只需要O(log n)个“步骤”，这是事实。但是，如果我们看一下常数因子，就会发现该对数的底数为2而不是10；并且二叉树通常是以红黑树的形式实现的，而红黑树在一般情况下并不是完全平衡的。（如果我没记错的话，它可能比log2(n)深多达两倍）

然而，真正推动差异的是有序映射的局部性较差。每个O(log n)步都涉及到一个无法预测的分支，这对指令流水线来说是不利的。更糟糕的是，它涉及到随机指针到内存的跟踪。现代CPU的经验法则是：“计算速度快，内存速度慢。”这是一个好的规则要记住，因为它变得越来越真实。CPU核心速度通常比内存速度提高得更快。

因此，除非您的映射足够小，可以适应缓存，否则这些随机指针解引用对整体性能非常不利。计算哈希只是数学运算（因此速度快），而追踪O(1)指针比追踪O(log n)指针更好；对于大的n来说，通常要好得多。

但是，哈希表优势的确切点再次取决于特定的系统。

- Nemo

O(log10 N) = O(lg2 N)。 log10N 和 lg2N 仅相差约3个常数因子。 - flight

1

@quasiverse：当然。红黑树的2x因子也只是“恰好”是一个常数因子。我的观点是，在这种情况下，这些常数很重要。这些不仅仅是算术运算;它们是随机内存访问，在现代系统上非常缓慢（相对而言）。 - Nemo

我不会在运行时对此发表评论。只是因为你说有“O(log n)步骤”，在这种情况下没有区别。如果你说，例如，“2 log n 步骤”，我就不会发表评论了。 - flight

@quasiverse：说得好。我之前的措辞让人觉得我不知道用对数改变基只是一个常数因子。我已经修改了我的措辞。谢谢。 - Nemo

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

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

- Darren Engwirda · Accepted Answer

正如你所说，基于哈希的映射表在查询时具有比二叉搜索树更快的渐近时间复杂度，可以达到O(1)，而不是O(log(N))。但这完全取决于使用的哈希函数在可允许的输入数据分布上的性能。

需要考虑哈希表的两种最坏情况：

1. 所有数据项生成相同的哈希索引，因此所有项都将进入同一个哈希桶 - 在这种情况下查询哈希表需要O(N)的时间。 2. 数据生成的哈希索引分布非常稀疏，因此大多数哈希桶为空。在这种情况下仍然可以实现O(1)的查询时间，但空间复杂度可能会在极限情况下变得无限制。

另一方面，二叉搜索树（至少是在大多数标准库实现中使用的红黑树）具有最坏情况下的O(log(N))时间和O(N)空间复杂度。

总之，如果您了解足够多关于输入数据的信息来设计“好”的哈希函数（避免碰撞过多，哈希桶分布不要太稀疏），那么使用哈希表通常是更好的选择。如果无法确保哈希函数在预期输入上的性能，则使用二叉搜索树。

哪种方法更好取决于具体问题和机器。希望这有所帮助。