Amazon Interview Question
Software Engineer / DevelopersHashtable
Advantage: retreival and insertion in O(1) time
Disadvantage: Space complexity can increase if size of input is not known.
Use: when lot of retreival of values or keys are required.
Binary Tree
Advantage: Space complexity is O(n)
Disadvantage: Time complexity is O(logn) for retrieval and O(nlogn) to create.
Use: when lot of traversal and comparison is required.
@shar3oob: rightly pointed out! Read the following for more,
- Saga Yao August 20, 2009#
The most important difference (besides hash tables being faster)
between hash tables and btrees is that hash tables only find on
equality searches.
Btrees can do range searches with things like <, >, <=, >=, between,...
#Binary search tree has worst case seek of O(n) if elements are inserted in order.
Hash table has worst case seek of O(n) if every element hashes to the same value.
Assuming you have a good hash functions, a hash table will be very close to O(1) for both inserts and look-ups.
If you balance your btree, you will end up with O(lg n) lookups.
For the same number of elements, a btree will usually be more compact.
However, a good hash table is notoriously hard to implement where as a good binary tree is, even balanced, is fairly straight forward. Hash functions are very subtle and finicky so picking a good one for your data set will take some work.