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

问题描述

哈希表总是比树快吗？虽然Hashtables具有O（1）搜索复杂性，但假设如果由于设计不当的哈希函数发生大量的冲突，并且如果我们使用链接结构（例如平衡树）来处理冲突，则搜索的最坏情况运行时间将为O（log n ）。即使在最坏的情况下，散列表总是比树更快，所以我可以得出大或小的数据集吗？还有如果我有足够的记忆，我不想要范围搜索，我可以随时去一个哈希表？

解决方案

哈希表总是比树更快吗？

不，不总是。这取决于许多事情，例如集合的大小，散列函数和一些哈希表实现 - 还有删除操作的数量。

哈希表平均每个 c O（1） - 但并不总是如此。

某些原因我可以在 想到当时喜欢树木：

1. 订购很重要。 [哈希表不维护订单，BST按定义排序]


2. 延迟是一个问题 - 您不能忍受可能发生的 O（n）。 [这可能对于实时系统至关重要]


3. Ther数据可能与您的哈希函数相关，并且许多元素散列到相同的位置[碰撞]不是不可取的。 [有时可以通过使用不同的哈希函数来解决]


4. 对于相对较小的集合 - 多次哈希表的 O（1）比树的高得多 - 对于小集合使用树可能会更快。



但是 - 如果数据是巨大的延迟不是一个问题，冲突是不可取的 - 哈希表比使用树更顺利。

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屋！