Amazon Interview Question Interns
Country: United States
Interview Type: Phone Interview
HashMap's lookup is faster O(1).
TreeMap internally uses a balanced binary tree to store keys in sorted order. Lookup is O(logn)
HashMap also uses more space, and can have degenerate cases (the lookup isn't strictly guaranteed to be O(1), and can be slower than a TreeSet for some degenerate cases). A TreeSet, as currently implemented in Java, gives you a hard guarantee of O(log n) performance.
Also what Godel said. A TreeSet keeps the keys in sorted order, according to some ordering that you would specify when creating the TreeSet (so you must be able to define some criteria, based on which the keys can be ordered). You might not care about the sortedness of the data for some applications, but it means that 1) the order of iteration when iterating through the data structure with an iterator (such as for (Type element: myTreeSet){....}) is well-defined (you cannot rely on any such thing for HashSets), and 2) if you need to, you can get the map sorted by key in O(n) time (once you already have the TreeSet).
HashMap is an unordered dictionary. average running time of all operations in HashMap is constant. TreeMap is an Ordered dictionary where all keys are ordered. They can be implemented using balanced binary search trees. So, all operations worst case running time would be O(logn).
Hash map will give O(1) lookup. Treemap requires O(logn) .
- isandesh7 January 23, 2013Hash map requires space equal to the number of possible keys.
But Treemap ionly requires space equal to the amount of keys currently stored.