https://dzone.com/articles/hashmap-vs-treemap-vs

1. Map Overview

There are 4 commonly used implementations of Map in Java SE - HashMap, TreeMap, Hashtable and LinkedHashMap. If we use one sentence to describe each implementation, it would be the following:

• HashMap is implemented as a hash table, and there is no ordering on keys or values.
• TreeMap is implemented based on red-black tree structure, and it is ordered by the key.
• LinkedHashMap preserves the insertion order
• Hashtable is synchronized, in contrast to HashMap.

This gives us the reason that HashMap should be used if it is thread-safe, since Hashtable has overhead for synchronization.

2. HashMap

If key of the HashMap is self-defined objects, then equals() and hashCode() contract need to be followed.

3. TreeMap

A TreeMap is sorted by keys. Let's first take a look at the following example to understand the "sorted by keys" idea.

4. Hashtable

From Java Doc: The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.

5. LinkedHashMap

LinkedHashMap is a subclass of HashMap. That means it inherits the features of HashMap. In addition, the linked list preserves the insertion-order. Let's replace the HashMap with LinkedHashMap using the same code used for HashMap.