HashMap And TreeMap

HashMap and TreeMap are the Map classes and both implements the Map interface. Map is an object that stores key-value pairs, where each key is unique and but there may be duplicate values. The HashMap class uses the hash table as a data structure. The TreeMap uses the red-black tree as a data structure. The main difference between HashMap and Treemap is that the HashMap does not preserve the any order whereas, the Treemap is ordered and sorted.

Difference between HashMap and TreeMap in Java 

1. Ordering : HashMap does not maintain any order. In other words , HashMap does not provide any guarantee that the element inserted first will be printed first.
Just like TreeSet , TreeMap  elements are also sorted according to the natural ordering of its elements . If TreeMap objects can not be sorted in natural order than use compareTo() method to sort the elements of TreeMap object.

2. Implementation : Internal HashMap implementation use Hashing.TreeMap internally uses Red-Black tree implementation.

3. Null keys and null value : HashMap can store one null key and many  null values.TreeMap can not contain null keys but may contain many null values.

4. Performance : HashMap  take constant time performance for the basic operations like get and put i.e O(1).According to Oracle docs , TreeMap provides guaranteed log(n) time cost for the get and put method.

5. Speed :   HashMap is much faster than TreeMap, as performance time of HashMap is constant against the log time TreeMap for most operations.

6. Functionality :   Just like TreeSet , TreeMap is rich in functionality. Functions like pollFirstEntry() , pollLastEntry() , tailMap() , firstKey() , lastKey() etc. are not present in HashMap.

7.  Comparison : HashMap uses equals() method in comparison while TreeMap uses compareTo() method for maintaining ordering.

8. Interfaces implemented : HashMap implements Map interface while TreeMap implements NavigableMap interface.

 

Similarities between HashMap and TreeMap in Java

1. Fail-fast iterators : The iterator's returned by the both class are fail-fast . Hence , if the object is modified after the iterator is created , in any way except through the iterator's own remove() method , the iterator will throw the ConcurrentModificationException.

2. Clone() method  : Both HashMap and TreeMap uses shallow copy technique to create clone of their objects.

3. Not Thread Safe :  Both HashMap and TreeMap class are unsynchronized . In other words , multiple threads can access the same object at a given time.
Although you can externally make both the classes synchronized :

HashMap :      Map m = Collections.synchronizedMap(new HashMap (...));
TreeMap :       Map m = Collections.synchronizedSortedMap(new TreeMap (...));

4. Package :  Both classes belong to the same package java.util and both are the members of the Java Collections Framework.

When to Use TreeMap over HashMap 

1. Sorted elements are required instead of unordered  elements. The sorted list return by TreeMap is always in ascending order.

2. TreeMap uses Red-Black algorithm underneath  to sort out the elements . When one need to perform read/write operations frequently , then TreeMap is a good choice.