Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
if you have key value pairs ... It depends on the range of hash(keys) that you want to store... If the range of Hash(keys) is high. Then hash map will take more space. and you are better of with treemap.. Also if there are huge number of collisions then space of hasmap is same as tree map. But complexity is more
From a java perspective, we may say that:
A TreeSet is backed by a TreeMap, and TreeMap.Entry has the following fields:
K key;
V value;
Entry<K, V> left = null;
Entry<K, V> right = null;
Entry<K, V> parent;
boolean color = BLACK;
the memory weight is 3 references + 1 boolean = 3 bytes + 1 bit (assuming we work on a 32 bits computer)
HashMap.Entry has the following fields:
final K key;
V value;
Entry<K, V> next;
final int hash;
the memory weight is 1 reference + 1 integer = 2 bytes
An additional memory weight in HashMap is due to an array of buckets, each bucket being addressed by the actual Entry.hash (which is the key hashCode). As one usually wish to have a minimum number of entries per bucket, let's assume we have exactly one entry in each bucket. There will thus be an array of N references (N: number of entries) so one byte per entry.
So I see a single bit of difference per entry between a TreeSet and a HashMap.
But this is implementation dependent. If you don't need your tree entries to reference their parent, then you spare 1 reference in the tree entry, and thus the tree becomes cheaper.
Generally speaking, BST needs N * (space of node) where N is number of node. However, HashTable( linear probing or chaining mechanism) needs more than N * (space of node) space to achieve a better performance, otherwise there will be too many collisions. So, overall, I will vote for BST for space efficiency at this case.
I mean it really depends on what kind of data you are talking about. These is very generic question. They both have different space complexity depends on what kind of data you trying to store. Is it e.g. Integers or Objects.
- Tiger February 15, 2013