Hash Table v/s Trees

6
votes

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?

4
algorithmdata-structureshashtreehashtable
I'm no expert, but I'd say it's situational. A lot of hashing functions are expensive, and for certain access patterns a tree is good. - Dan Fego
"Always" is such a big all-encompassing word. Any chance you could edit this question to reduce it to something a bit more specific, like specific scenarios (only)? Otherwise it will almost certainly be closed as not-constructive. - Lasse V. Karlsen
Lot of people here have mentioned that the worst case would be O(N). How can it be O(n) if the collisions are handled using a balanced tree structure instead of a linked list. Worst case to search across a balanced tree like AVL would be O(log n) - avinash shah
@avinashshah You can reduce the worst case search case by using some other overflow data structure, but you don't get O(lg n) search for free. It comes at the cost of O(lg n) insert, since you are now inserting into a tree or similar that in the worst case contains all the elements. In almost all applications that trade off just isn't worth it. - verdesmarald

4 Answers

10
votes

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.

1
votes

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(n) (not O(log n)). Therefore you cannot conclude for big or small data sets even in case of worst case scenarios hash tables will always be faster than trees.

0
votes

Use hashtable, and init it with the proper dimension. For example if you use only half space the collisions are very few.

0
votes

In worst case scenario you'll have O(n) time in hast-tables. But this is a billions less probable then sun exploding write now, so when using a good hash-function you can safely assume it works in O(1) unless sun explodes.
On the other hand, performance of both Hash-Tables and Trees can vary on implementation, language, and phase of the moon, so the only good answer to this question is "Try both, think and pick better".