What are the differences between a HashMap and a TreeMap in Java?

Interview question: What are the differences between a HashMap and a TreeMap in Java?

Both HashMap and TreeMap are data structures that allow the storage of key value pairs in Java. They are defined as a part of the Java Collections framework which is a part of core Java. They exist under the package java.util. The choice between whether to use a HashMap or a TreeMap is largely dependent upon the data being stored and how the data will be accessed. Let us look at the properties of each:

HashMap:

1. HashMap does not maintain insertion order of data.

2. HashMap is not synchronized so data operations perform very quickly.

3. The algorithmic complexity of the get, put, and remove operations in Big-O notation are all O(1).

4. Items inserted into the HashMap must override the hashCode() method in Object in order to minimize hash key collisions.

TreeMap:

1. TreeMap maintains a natural ordering of data.

2. Although TreeMap is not synchronized, it does have slower performance due to the necessity of having to sort the data on insertion and to traverse the tree on retrieval.

3. The algorithmic complexity of the get, put, and remove operations in Big-O notation are all O(log(n)).

4. A comparator must be supplied to a TreeMap so that a natural ordering can be established.

When to use a HashMap versus a TreeMap comes down to whether or not the natural ordering of the elements needs to be maintained or not. When they do not, it is almost always preferable to use a  HashMap. When they do, you must use a TreeMap.