Monday, August 24, 2015

Difference between HashMap, LinkedHashMap and TreeMap in Java

The java.util.Map is one of the most important interfaces from Java Collection Framework.  It provides hash table data structure functionality by its implementations like HashMap, Hashtable, LinkedHashMap and a little bit of sorting with the TreeMap. So if you are looking to store key-value pairs in Java program,  you have a wide range of choices available depending upon your requirement. The main difference between LinkedHashMap, TreeMap and HashMap comes in their internal implementation and specific features, which makes them useful in certain scenarios. For example, the HashMap is a general purpose Map (hash table data structure), which should be used whenever you need a hashing-based data structure for storing your mappings (key-value pairs).

TreeMap is a Red-Black tree based NavigableMap implementation provides you sorting, on top of hashing offered by Map interface. This means you can not only retrieve elements in guaranteed log(n) time (Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms), but also iterate through those mapping in a predefined sorted order, but you need to pay a heavy price to keep mappings in sorted order.

Difference between HashMap and TreeMap in Java

On the other hand, LinkedHashMap is a compromise between these two, it doesn't provide sorting but unlike HashMap, it provides ordering e.g. maintaining mappings in an order they are inserted into Map, known as insertion order or order on which they are accessed, called access order.

Apart from these three popular Map implementation, you also have some special purpose Map implementations e.g. EnumMap for storing mapping with enum constants as keys,  it is highly optimized for enum constants. You also have a special map called WeakHashMap for creating a Garbage Collector friendly Cache, where values become eligible for garbage collection as soon as there is no other reference to them apart from keys in WeakHashMap.

Then there is IdentityHashMap for creating a Map which uses identity instead of equality for comparing keys since identity equality is rare, you get less number of collisions on this Map and finally, JDK 5 introduced ConcurrentHashMap for better scalability in a multi-threaded environment, where the number of reader threads clearly outnumbers a number of writer threads.

LinkedHashMap vs TreeMap vs HashMap

Though all three classes implement java.util.Map interface and follows general contract of a Map interface, defined in terms of equals() and hashCode() method, they also have several differences in terms of Ordering, Sorting, permitting null elements, Iteration, Performance, Speed and internal implementation. Let's have a quick look on each of these properties.

Ordering and Sorting

HashMap doesn't provide any ordering guarantee for entries, which means, you can not assume any order while iterating over keys and values of HashMap. This behavior of HashMap is similar to Hashtable while other two Map implementation provides ordering guarantee.

LinkedHashMap can be used to maintain insertion order, on which keys are inserted into Map or it can also be used to maintain an access order, on which keys are accessed. This provides LinkedHashMap an edge over HashMap without compromising too much performance.

TreeMap provides you complete control over sorting elements by passing custom Comparator of your choice, but with the expense of some performance. Since entries are stored in a tree-based data structure, it provides lower performance than HashMap and LinkedHashMap.

Null keys and Values

HashMap allows one null key and multiple null values. It keeps null key based entries on index[0] on an internal bucket. If you look at the put() method of HashMap, you can see, it doesn't throw NullPointerException for null keys. Since LinkedHashMap is a subclass of HashMap, it also allows null keys and values.

On the other hand, TreeMap, which sorts elements in natural order doesn't allow null keys because compareTo() method throws NullPointerException if compared with null. If you are using TreeMap with user defined Comparator than it depends upon the implementation of compare() method.


Iterators returned by all these Map's collection view methods e.g. values() or keySet() is fail-fast iterators, which means they will throw ConcurrentModificatoinException if Collection is modified structurally once Iteration begins, except by using remove() method of Iterator.

By the way, it's worth remembering that apart from adding or removing more mappings, it can also be any operation which affects iteration order of LinkedHashMap. In access-ordered LinkedHashMap, even querying the Map with get() method is a structural modification, because it changes the iteration order, on the other hand updating the value in an insertion-ordered linked hash map is not a structural modification.

Finally, the fail-fast behavior is not guaranteed, and they throw ConcurrentModificationException on the best-effort basis, which means do not write code, which depends upon this behavior. It should only be used to detect programming bugs.

Performance and Speed

Since HashMap is a barebone implementation of java.util.Map interface, it provides constant time performance for the get() and put() operation, where put() method is used to store entries (key-value pairs) and get() is used to retrieve a value based on a key.

BTW, constant time performance is only provided if mappings are distributed uniformly across bucket location. In the real world, you always have collision and HashMap handles collision by using a linked list to store collided elements. This can reduce worst case performance of HashMap up to O(n).

To mitigate the above performance issue, JDK 8 has introduced balanced tree instead of linked list in case of frequent collision in HashMap. It internally switches to balanced tree from linked list if there are more than 8 entries in one bucket. See how does HashMap handles collisions in Java for more details.

Worth noting is that this behavior is only applicable to HashMap, LinkedHashMap, and ConcurrentHashMap, Hashtable is left behind to preserve its legacy iteration order as many legacy Java application relies on that and this changes that order. This is also a good example of why you should not rely on undocumented features of JDK e.g. iteration order of HashMap because they can change in future.

but HashMap is certainly faster than Hashtable because it's not synchronized. Iteration over Map is directly proportional to the "capacity" + "size" of HashMap, that's why it's important to set the initial capacity high enough if iteration performance is important. You can further use initial capacity and load factor to fine tune your HashMap performance, to avoid rehashing of HashMap.

TreeMap is  so it's costlier than HashMap if the order is not concerned. Since TreeMap is based on tree data structure (based upon Red-Black tree), it provides the log(n) time for the get(), put(), containsKey() and remove() operation, Algorithms are based upon those given in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

Difference between TreeMap and LinkedHashMap in Java

LinkedHashMap is a trade-off between two, like HashMap it also provides constant time performance for add, contains and remove, though it's slightly slower than HashMap, to maintain linked list. By the way, looping over Map in the case of LinkedHashMap is slightly faster than HashMap because the time required is proportional to size only. So if you need insertion order or access order, consider using LinkedHashMap over TreeMap in Java.

Thread-safety and Synchronization

All three Map implementation are not thread-safe, which means you can not use them safely in a multi-threaded application. Though you can synchronize them externally by using Collections.synchronizedMap(Map map) method. Alternatively, you can also use their concurrent counterpart e.g. ConcurrentHashMap which is also a better choice than HashMap in a concurrent Java application.

When using synchronized Map e.g. synchronized LinkedHashMap or SortedMap, you must do at the time or creating the map to prevent accidental non-synchronized access. You can use the following idiom to create Synchronized Map in Java:

Synchronized LinkedHashMap
Map<Integer, Integer> numbers = Collections.synchronizedMap(new LinkedHashMap<>());

Synchronized TreeMap
SortedMap<Integer, String> sorted = Collections.synchronizedSortedMap(new TreeMap<>());

Remember to use Collections.synchronizedMap() for synchronizing HashMap, LinkedHashMap and Collections.synchronizedSortedMap() method for synchronizing TreeMap. If you are not comfortable then see this guide on how to synchronize HashMap in Java.

Internal Implementation

TreeMap is Red-Black tree based NavigableMap implementation while HashMap is internally backed by an array. It uses index[0] to store entries corresponding to null keys. In fact, questions related to the inner working of HashMap is very popular in Java, for example, How does get() method of HashMap works internally is one of the frequently used questions to Senior Java developers.

On the other hand, LinkedHashMap extends HashMap and uses linked list to provide insertion order guarantee. It uses doubly-linked list running through all of its entries, which can also be used to maintain access-order. Remember, insertion order is not affected if a key is re-inserted into LinkedHashMap, but access order is affected if LinkedHashMap is created to maintain access-order.

TreeMap is internally based upon Red-Black Tree and NavigableMap, introduced in JDK 6. The Red-Black tree is used to maintain the sorting order imposed by Comparable or Comparator, provided at the time of creation.  TreeMap provides guaranteed log(n) time cost for the get, put, containsKey and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

When to use LinkedHashMap, TreeMap, and HashMap

You can use a LinkedHashMap when you need to keep your mappings in either insertion order or access order. LinkedHashMap by default keeps elements in the order, on which they are inserted, and this order is reflected when you traverse over LinkedHashMap, but it also provides a constructor, which allows you to keep entries in access order, the. order in which they are accessed. One of the clever use of Java LinkedHashMap is to use it as Least Recently Use or LRU Cache.

TreeMap is your go to map implementation if you want to keep keys  in a sorted order, either in their natural order defined by Comparable interface or a custom order imposed by Comparator interface, though it's worth remembering that your compareTo() or compare() method must be consistent with equals() method, because Map interface is defined in terms of equals and TreeMap uses compareTo for comparing keys. So if keys compare() or compareTo() implementation is not consistent, then it will fail to obey Map's general contract.

HashMap is your general purpose hashing based collection, whenever you need to use a hash table data structure in Java to store key-value pairs, the first choice goes to HashMap in a single threaded environment. If you happened to use a Map in a multi-threaded environment consider using Hashtable, synchronized HashMap or ConcurrentHashMap from Java Collection Framework.

Since LinkedHashMap solved the problem of chaotic ordering provided by Hashtable and HashMap, without incurring the high cost associated with TreeMap, you can also use LinkedHashMap to create a copy of a Map in Java, as shown in below example.

An example of using LinkedHashMap, TreeMap and HashMap in Java

Let's see an example of how to use these Map implementations. In this example, we will use HashMap to create a general purpose Cache, TreeMap to create a sorted Cache and we will use LinkedHashMap for copying a Map (cache) and maintaining orders in the original Map.

import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;

  * Java Program to demonstrate How to use LinkedHashMap, TreeMap and HashMap.
  * It shows that HashMap doesn't guarantee any order, TreeMap keeps them in 
  * sorted order determined by default using Comparable or explicit Comparator
  * provided by client, and LinkedHashMap also keep mapping in order they
  * are added or accessed., 
  * @author Javin Paul
public class MapTest {    
    public static void main(String args[]){
        //Using HashMap as general purpose single threaded cache
        Map<Integer, String> cache = new HashMap<>();
        cache.put(1, "Stuart");
        cache.put(2, "Steven");
        cache.put(3, "James");
        cache.put(4, "Ian");
        System.out.printf("Name of Employee with id %d is %s %n", 1, cache.get(1));
        System.out.println("Order of Entries in HashMap - Not guaranteed");
        //Using TreeMap to create a sorted cache, sorting keys on reverse order
        SortedMap<Integer, String> sortedCache = new TreeMap<>(Collections.reverseOrder());
        System.out.println("Order of Entries in TreeMap - Sorted in reverse order");
        //Using LinkedHashMap to create copy of a Map in Java
        Map<Integer, String> copy = new LinkedHashMap<>(sortedCache);
        System.out.println("Order of Entries in a copy Map created by LinkedHashMap");

Name of Employee with id 1 is Stuart

Order of Entries in HashMap - Not guaranteed
{1=Stuart, 2=Steven, 3=James, 4=Ian}

Order of Entries in TreeMap - Sorted in reverse order
{4=Ian, 3=James, 2=Steven, 1=Stuart}

Order of Entries in a copy Map created by LinkedHashMap
{4=Ian, 3=James, 2=Steven, 1=Stuart}

You can see that TreeMap has sorted mappings in reverse order, because of reverse Comparator provided to it. Also, LinkedHashMap has created a copy of TreeMap and order of entries are retained.


Here is the summary of differences between HashMap, LinkedHashMap, and TreeMap in Java:

Difference between TreeMap, LinkedHashMap and HashMap in Java

That's all on the difference between LinkedHashMap, TreeMap, and HashMap in Java. Though all three are Map implementation, they have a different purpose and used accordingly. Use LinkedHashMap, if you need to maintain insertion or access order of mappings e.g. in LRU Cache. Use TreeMap, if you need to maintain mappings in a sorted order, either in their natural order or a custom order defined by Comparator and use HashMap for all your general purpose hashing based collection requirement. HashMap allows you to retrieve an object in O(1) time if you know the key.

Further Learning
Java Fundamentals: The Java Language by Jim Wilson
Java Fundamentals: Collections
Head First Java

Other Java Collection interview questiosn you may like
If you like this article and want to know more about other Collection classes, do check following interview questions analysis and explanation from Java Collection framework:
  • What is the difference between HashSet, TreeSet, and LinkedHashSet in Java? (answer)
  • What is the difference between HashMap and ArrayList in Java? (answer)
  • What is the difference between HashSet and ArrayList in Java? (answer)
  • 5 differences between HashMap and Hashtable in Java? (answer)
  • What is the difference between ArrayList and LinkedList in Java? (answer)
  • How to use NavigableMap in Java 6? [example]
  • How to use BlockingQueue in Java Program? [example]
Thanks for reading this article so far. If you like this article then please share with your friends and colleagues. If you have any questions or feedback then please drop a comment.


Claude Martin said...

"HashMap allows you to retrieve object in O(1) time, if you know key."
That's only true if you have some perfect hashing function. Worst case is O(n). But on average it really is near constant.
Another concurrent implementation is ConcurrentSkipListMap. It can be used like a TreeMap.

Unknown said...

“TreeMap provides you sorting, on top of hashing offered by Map interface, which means you can not only retrieve elements in constant time i.e. O(1) time, but also iterate through those mapping in a predefined sorted order”
TreeMap doesn't allow to extract element in constant time.

Javin Paul said...

@Unknown, Thanks for spotting that error. You are right, TreeMap doesn't provide constant time operation, instead it guaranteed log(n) time cost for get, put, containsKey and remove operation.

GOPI said...

GReat article with great info:) Thank you Javin:)

Nitin Chavan said...

"The java.util.Map is one of the most important interfaces from Java Collection Framework." As per my understanding Maps are not part of java collection framework.

Javin Paul said...

Hello Nitin, they are definitely part of Java Collection framework, its just that they don't implement Collection interface.

Post a Comment