哈希表V / S树 [英] Hash Table v/s Trees

问题描述

是哈希表总是比树快？虽然哈希表有O（1）搜索的复杂性，但如果由于设计不佳的散列函数很多冲突的发生，如果我们处理采用链式结构（比如一个平衡树），然后运行时间搜索最坏的情况下会为O冲突（日志N猜想）。所以，我可以断定为或大或小的数据集，即使在情况最坏的情况下哈希表总比树快？另外，如果我有足够的内存和我不想要范围的搜索，我可以经常去的一个哈希表？

解决方案

  

是哈希表总是比树快？

不，不是的总是的。这取决于许多因素，如集合的大小，散列函数，而对于一些哈希表的实现 - 删除OPS还数

哈希表是 O（1）每运的平均的 - 但事实并非总是如此。他们可能是 O（N）中的最坏的情况下的。

某些原因，我能想到的此刻preFER树：

1. 在顺序很重要。 [哈希表不维持秩序，BST被定义排序]
2. 延迟是一个问题 - 你也不能苦了为O（n ）可能发生的。 [这可能是实时系统中的关键]
3. 疗法的数据可能是类似的关系到你的哈希函数，和散列到同一地点的许多元素[碰撞]不是unprobable。 [这可以通过使用不同的哈希函数来有时解决]
4. 对于小集合 - 很多时候哈希表的 0的隐藏的常数（1）远远高于树的 - 并用一棵树可能会更快对小集合。

然而 - 如果数据是巨大的，等待时间不是一个问题和碰撞是unprobable - 哈希表渐近更好然后用树

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.

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:

1. Ordering is important. [hash-tables are not maintaining order, BST is sorted by definition]
2. Latency is an issue - and you cannot suffer the O(n) that might occur. [This might be critical for real-time systems]
3. 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]
4. 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.

这篇关于哈希表V / S树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！