Java: HashMap vs. TreeMap vs. Hashtable vs. LinkedHashMap

Map is one of the most important data structures. In this post, I shall show you the main differences between HashMap, TreeMap, HashTable and LinkedHashMap.

There are four 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 a hash table without ordering on keys, and with amortized constant access costs.
TreeMap is a hash table allows to access entries based on key ordering with logarithmic costs.
LinkedHashMap is a hash table using a linked list to preserve the insertion order of entries.
Hashtable is the thread-safe version of HashMap without nullable values.

We give more specific remarks concerning the use of maps below.

HashMap

If you want to use self-defined objects as keys, make sure the equals and hashCode methods implemented correctly. By default, the hashCode and equals methods implemented in Object class are used. The default hash codes are distinct for distinct objects, and two keys are equal only if they have the same primitive value or they are references to the same object.

TreeMap

Keys for TreeMap must implement Comparable interface, since they have to compare with each other. Note that TreeMap uses compareTo other than equals to decide whether two keys are identical. Another difference between TreeMap and the other map implementations is that it provides guaranteed O(lgn) time cost for the containsKey, get, put and remove operations, while others guarantee amortized O(1) time cost (O(n) in the worst case) for these operations.

Hashtable

The Hashtable class is roughly equivalent to HashMap, except that it is synchronized and it does not permit null keys or null values.

LinkedHashMap

LinkedHashMap is a subclass of HashMap. It inherits the features of HashMap and, in addition, the output of the entrySet method preserves the insertion/access-order of the entries. There is also a special method removeEldestEntry that allows implementer to erase entries according to custom criteria. One direct application of LinkedHashMap in computer science is the LRU (least-recently-used) cache (example code).