哈希表与树 [英] Hash Table v/s Trees
问题描述
哈希表总是比树快吗?尽管哈希表的搜索复杂度为 O(1)，但假设由于散列函数设计不当，会发生大量冲突，并且如果我们使用链式结构(例如平衡树)处理冲突，那么搜索的最坏情况运行时间将是 O(log n).那么，即使在最坏的情况下，我是否可以得出大数据集或小数据集的结论，哈希表总是比树快?另外，如果我有足够的内存并且不想进行范围搜索，我可以随时使用哈希表吗?
Are hashtables always faster than trees? Though Hashtables have O(1) search complexity but suppose if due to badly designed hash function lot of collisions happen and if we handle collisions using chained structure (say a balanced tree) then the worst case running time for search would be O(log n). So can I conclude for big or small data sets even in case of worst case scenarios hash tables will always be faster than trees? Also If I have ample memory and I dont want range searches can I always go for a hash table?
推荐答案
哈希表总是比树快吗?
Are hashtables always faster than trees?
不，不是总是.这取决于很多因素，例如集合的大小、散列函数以及某些散列表实现 - 以及删除操作的数量.
No, not always. This depends on many things, such as the size of the collection, the hash function, and for some hash table implementations - also the number of delete ops.
哈希表是 O(1) 每个操作平均 - 但情况并非总是如此.在最坏的情况中，它们可能是O(n).
hash-tables are O(1) per op on average - but this is not always the case. They might be O(n) in worst cases.
目前我能想到的一些偏爱树木的原因:
Some reasons I can think of at the moment to prefer trees:
- 订购很重要.[哈希表不维护顺序，BST按定义排序]
- 延迟是一个问题 - 您不能忍受
O(n)可能发生的.[这可能对实时系统至关重要] - 这些数据可能与您的散列函数相似"，并且许多元素散列到相同位置 [碰撞] 并非不可能.[这有时可以通过使用不同的哈希函数来解决]
- 对于相对较小的集合 - 很多时候哈希表的
O(1)之间的隐藏常数比树高得多 - 对于小集合，使用树可能会更快.
- Ordering is important. [hash-tables are not maintaining order, BST is sorted by definition]
- Latency is an issue - and you cannot suffer the
O(n)that might occur. [This might be critical for real-time systems] - Ther data might be "similar" related to your hash function, and many elements hashed to the same locations [collisions] is not unprobable. [this can be sometimes solved by using a different hash function]
- For relatively small collections - many times the hidden constant between hashtable's
O(1)is much higher then the tree's - and using a tree might be faster for small collections.
但是 - 如果数据很大，延迟不是问题并且碰撞是不可能的 - 哈希表比使用树渐近更好.
However - if the data is huge, latency is not an issue and collisions are unprobable - hash-tables are asymptotically better then using a tree.
这篇关于哈希表与树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
