散列表总是比树更快吗？虽然散列表具有O(1)的搜索复杂度，但是如果由于糟糕的设计而发生了许多冲突，如果我们使用链式结构（例如平衡树）来处理冲突，则搜索的最坏情况运行时间将为O(log n)。所以我可以得出结论，在大或小数据集的情况下，即使在最坏情况下，散列表也总是比树更快吗？此外，如果我有充足的内存并且不想进行范围搜索，我是否总是可以选择散列表？
4个回答
10
“哈希表总是比树快吗？”
不，不总是。这取决于很多因素，例如集合的大小、哈希函数以及对于某些哈希表实现-还有删除操作的数量。
哈希表在平均情况下每个操作的时间复杂度为O(1)，但并非总是如此。它们在最坏情况下可能会变成O(n)。
目前我能想到的一些偏向使用树的原因：
- 排序很重要。[哈希表不维护顺序，BST根据定义排序]
- 延迟是一个问题-您不能承受可能发生的
O(n)。[这对于实时系统可能是关键] - 数据可能与您的哈希函数相关“相似”，并且许多元素散列到相同的位置[冲突]并不罕见。[这有时可以通过使用不同的哈希函数来解决]
- 对于相对较小的集合-许多时候哈希表的隐藏常数比树的高得多-使用树可能更快。
但是-如果数据很大，延迟不是问题，并且冲突不太可能-哈希表在渐近意义下比使用树更好。
- amit
6
经常情况下，由于缓存一致性（无论是来自主内存还是磁盘），精心打包的树可以比哈希表表现更好。在这种情况下，数据量大小并不重要——根据您使用字典结构的方式，哈希表可能不是最佳选择。 - Kaganar
哈希表是什么？开放定址法哈希表还是“桶”哈希表？带或不带增量调整？还是基于线性哈希？有这么多的哈希表实现！你的答案对于其中一些是错误的，所以请尽可能精确。 - Matthieu M.
@MatthieuM.：这些都是几乎所有哈希表的传统缺点，即使使用开放地址法或链式哈希表作为“桶”也是如此。排序是一个缺点，因为哈希不能保证顺序不变。延迟是一个问题，由于最坏情况（如果由于某些限制你不能承受任何
O(n)操作-这是一个问题），相似的哈希值并不是真正的缺点，因为可以通过选择不同的哈希函数轻松解决，而大小问题通常是由于哈希函数开销引起的，如果我记得正确的话。你具体有什么问题？ - amit@amit：不，除了排序（显然），它们并不相同。例如延迟在这里没有明确定义。我可以保证使用哈希表（使用增量调整大小）进行O（1）插入，而对于BST，我将经常重新平衡，因此最坏情况下为O（log N）。但是，无法保证O（1）查找；但是通过将BST用作桶结构，我可以获得O（log N）。小型集合同样可以从开放地址哈希表中受益：每个节点的开销更小，单个块分配=>比BST更好的CPU缓存行为！因此，并非所有评论都适用于所有实现。 - Matthieu M.
@MatthieuM.：好的，我明白你的意思了。确实，没有万能的解决方案，是的 - 有一些解决方法可以解决“传统”DS的一些问题（例如将BST作为bucket），但确实没有一个适用于所有情况，但这些都是在选择DS时应考虑的问题。 - amit
@amit：是的，我同意。我的基本建议是选择BST。它更简单，工作可靠。当性能成为问题时，我们再考虑权衡，届时我们会有更多信息 :) - Matthieu M.
1
如果由于设计不良的哈希函数导致大量冲突发生，并且我们使用链式结构（比如平衡树）来处理冲突，那么搜索的最坏情况运行时间将是 O(n)（而不是 O(log n)）。因此，即使在最坏情况下，对于大或小数据集，哈希表也不一定总是比树更快。
- Franck Dernoncourt
0
使用哈希表，并使用适当的维度进行初始化。例如，如果您只使用一半的空间，则冲突非常少。
- dash1e
0
在最糟糕的情况下，哈希表的时间复杂度为O(n)。但是这比太阳现在爆炸的可能性要低上亿倍，所以当使用一个好的哈希函数时，你可以安全地假设它的时间复杂度为O(1)，除非太阳爆炸。
另一方面，哈希表和树的性能可能因实现、语言和月亮的阶段而有所不同，所以对于这个问题唯一好的答案是"试试两种方法，思考并选择更好的"。
- kilotaras
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
O(lg n)的搜索效率。这要付出插入成本为O(lg n)的代价，因为现在你正在插入到一棵树或类似的数据结构中，该数据结构在最坏情况下包含所有元素。在几乎所有应用程序中，这种权衡都不值得。 - verdesmarald