CODEWITHSUNDEEP
javadata-structurestreesizehashtable
stillAFanOfTheSimpsons
stillAFanOfTheSimpsons

Reputation: 173

When to use hash table?

I have a general question about when we should use hash table instead of say AVL trees. I remembered my lecturer saying if the data size is something like 210 or 220, a AVL tree is acceptable, because using hash table will generate hashing operations etc.

So I wonder in practice, is there a general rule regarding data size to tell us when we should choose hash table over AVL trees? Is hash table always the first choice when dealing with data size larger than 220?

Upvotes: 0

Views: 116

Answers (1)

Will Whitaker
Will Whitaker

Reputation: 26

Hash tables are 'wasteful' memory wise as the backing table is normally larger than the number of entries. Trees don't have this problem but do have the problem that lookups (and most other operations) are a log(n) operation. So yes you are correct that for small data sets a tree may be better - depending on how much you care about memory efficiency.

There's no general rule data regarding data size - it depends on the specifics of the implementations you are comparing and what you want to optimize for (memory or CPU). The Javadocs provide some insight into the performance of the implementations provided by Java:

http://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html http://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html

Beyond that writing some benchmarks and comparing different implementations will give you more insight.

Upvotes: 1

Related Questions