哈希表总是比树快吗？虽然哈希表具有 O(1) 的搜索复杂性，但假设如果由于设计不良的哈希函数发生大量冲突，并且如果我们使用链式结构（例如平衡树）处理冲突，那么搜索的最坏情况运行时间将是 O(log n ）。因此，即使在最坏的情况下，我是否可以得出大数据集或小数据集的结论，哈希表总是比树快？另外，如果我有足够的内存并且我不想进行范围搜索，我可以一直使用哈希表吗？
问问题
4208 次
4 回答
10
哈希表总是比树快吗？
不，并非总是如此。这取决于很多事情，例如集合的大小、散列函数以及某些散列表的实现——还有删除操作的数量。
哈希表平均O(1)每个操作- 但情况并非总是如此。他们可能在最坏的情况下。O(n)
目前我能想到的一些喜欢树木的原因：
- 订购很重要。【hash-tables不维护顺序，BST按定义排序】
- 延迟是一个问题——你不能忍受
O(n)可能发生的事情。[这可能对实时系统至关重要] - 数据可能与您的散列函数“相似”，并且许多元素散列到相同位置 [冲突] 并非不可能。[这有时可以通过使用不同的哈希函数来解决]
- 对于相对较小的集合 - 哈希表之间的隐藏常数很多时候
O(1)比树的高得多 - 对于小型集合，使用树可能更快。
但是 - 如果数据很大，延迟不是问题，并且冲突是不可能的 - 哈希表在渐近上比使用树更好。
于 2012-04-05T17:56:30.093 回答
1
如果由于设计不良的哈希函数发生了很多冲突，并且如果我们使用链式结构（比如平衡树）处理冲突，那么搜索的最坏情况运行时间将是O(n)（而不是 O(log n)）。因此，即使在最坏的情况下，您也无法得出大数据集或小数据集的结论，哈希表总是比树快。
于 2012-04-05T17:56:38.267 回答
0
使用哈希表，并使用适当的维度对其进行初始化。例如，如果您仅使用一半空间，则碰撞很少。
于 2012-04-05T17:55:28.610 回答
0
在最坏的情况下，您将在 hast-tables 中有 O(n) 时间。但这比现在 sun exploding write 的可能性要小数十亿，所以当使用一个好的散列函数时，你可以放心地假设它在 O(1) 中工作，除非 sun 爆炸。
另一方面，哈希表和树的性能可能因实现、语言和月相而异，所以这个问题的唯一好的答案是“尝试两者，思考并选择更好”。
于 2012-04-05T17:55:39.910 回答