Difference between HashMap, LinkedHashMap and TreeMap in Java

Map is one of the most important data structure from Java Collection Framework.  It provides hash table data structure functionality with it's rich implementations like HashMap, Hashtable, LinkedHashMap and little bit of sorting with TreeMap. So if you are looking to store key value pairs in Java program,  you have wide range of choices available depending upon your requirement. Main difference between LinkedHashMap, TreeMap and HashMap comes in there internal implementation and specific features, which makes them useful in certain scenarios. For example, 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 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, but you need to pay heavy price to keep mappings in sorted order. 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 a 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 collision on this Map and finally JDK 5 introduced ConcurrentHashMap for better scalability in multi-threaded environment, where number of reader threads clearly out numbers number of writer threads.

LinkedHashMap vs TreeMap vs HashMap

Though all three classes implements 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 property.

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 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 internal bucket. If you look at put() method of HashMap, you can see, it doesn't throw NullPointerException for null keys. Since LinkedHashMap is a sub class 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 implementation of compare() method.

Iterators

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 value in a insertion-ordered linked hash map is not a structural modification.

Finally, fail-fast behavior is not guaranteed, and they throw ConcurrentModificationException on 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 bare bone implementation of java.util.Map interface, it provides constant time performance for get() and put() operation, where put is used to store key value pair and get is used to retrieve value based upon key. BTW, constant time performance is only if mappings are distributed uniformly across bucket location, 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.

Since TreeMap is based on tree data structure, it provides log(n) time for get(), put(), containsKey() and remove() operation, so it's costlier than HashMap, if order is not concerned.

LinkedHashMap is a trade-off between two, like HashMap it also provides constant time performance for add, contains and remove, though its slightly slower than HashMap, to maintain linked list. By the way Iteration over Map in case of LinkedHashMap is slightly faster than HashMap, because 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 synchronized them externally by using Collections.synchronizedMap(Map map) method. Alternatively you can also use there concurrent counter part 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 map to prevent accidental non synchronized access. You can use 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 inner working of HashMap is very popular in Java, for example How 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 it's 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.

When to use LinkedHashMap, TreeMap and HashMap in Java

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, i.e. 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 there 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, first choice goes to HashMap in 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 problem of chaotic ordering provided by Hashtable and HashMap, without incurring high cost associated with TreeMap, you can also used 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");
        System.out.println(cache);
       
        //Using TreeMap to create a sorted cache, sorting keys on reverse order
        SortedMap<Integer, String> sortedCache = new TreeMap<>(Collections.reverseOrder());
        sortedCache.putAll(cache);
        System.out.println("Order of Entries in TreeMap - Sorted in reverse order");
        System.out.println(sortedCache);
       
        //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");
        System.out.println(copy);
       
    }
}

Output:
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.

Summary

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

That's all on difference between LinkedHashMap, TreeMap and HashMap in Java. Though all three are Map implementation, they have 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 there 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 object in O(1) time, if you know key.


Further Reading
If you are really serious about mastering various classes from Java Collection framework then I suggest you to read following two books, both of them are classic and highly recommended for experienced Java developer who wants to constantly improve their skill and knowledge of Java API.

• Java Generics and Collection By Maurice Naftalin (see here)
• Effective Java 2nd Edition by Joshua Bloch (see here)

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 difference between HashSet, TreeSet and LinkedHashSet in Java? (answer)
• What is difference between HashMap and ArrayList in Java? (answer)
• What is difference between HashSet and ArrayList in Java? (answer)
• 5 differences between HashMap and Hashtable in Java? (answer)
• What is difference between ArrayList and LinkedList in Java? (answer)
• How to use NavigableMap in Java 6? [example]
• How to use BlockingQueue in Java Program? [example]