哈希表v/s树

Question

哈希表总是比树快吗？虽然Hashtables具有O(1)搜索复杂度但是假设由于设计错误的哈希函数发生了大量冲突,并且如果我们使用链式结构(比如平衡树)处理冲突,那么搜索的最坏情况运行时间将是O(log n) ).因此,即使在最坏情况下哈希表总是比树更快,我能否得出大或小数据集的结论？此外,如果我有足够的内存,我不想要范围搜索,我可以总是去哈希表吗？

Answer 1

哈希表总是比树快吗？

不,不总是.这取决于许多因素,例如集合的大小,散列函数,以及一些散列表实现 - 还有删除操作的数量.

散列表平均O(1)每个操作- 但情况并非总是如此.他们可能是在最坏的情况下.O(n)

我现在可以想到更喜欢树木的一些原因:

1. 订购很重要.[哈希表不维护顺序,BST按定义排序]
2. 延迟是一个问题 - 你不能忍受O(n)可能发生的事情.[这可能对实时系统至关重要]
3. Ther数据可能与您的哈希函数"相似",并且许多元素散列到相同位置[collisions]并非不可能.[这有时可以通过使用不同的哈希函数来解决]
4. 对于相对较小的集合 - 很多时候哈希表之间的隐藏常量O(1)远高于树的集合 - 并且对于小集合使用树可能更快.

但是 - 如果数据很大,延迟不是问题而且冲突是不可能的 - 哈希表比使用树更渐进.