Difference between HashMap, LinkedHashMap and TreeMap in Java with Example

Hello guys, if you are wondering what is difference between HashMap, TreeMap, and LinkedHashMap in Java and when to use them then you are at the right place. In past, I have shared frequently asked HashMap Interview questions and ConcurrentHashMAp Interview questions and today, I Will answer this question in detail. The java.util.Map is one of the most important interfaces from the 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 the 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 a Java programmer should know to use them effectively. 

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 that provides you sorting, on top of hashing offered by the 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.

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 implementations, 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.

Difference between LinkedHashMap vs TreeMap vs HashMap in Java with Examples

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 at each of these properties.

1. 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 the other two Map implementation provides an 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 a 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.

2. 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 the compareTo() method throws NullPointerException if compared with null. If you are using TreeMap with a user-defined Comparator then it depends upon the implementation of compare() method.

3. 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 that affects the 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.

4. 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 the 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 locations. In the real world, you always have collision, and HashMap handles collision by using a linked list to store collided elements. This can reduce the worst-case performance of HashMap up to O(n).

To mitigate the above performance issue, JDK 8 has introduced a balanced tree instead of a linked list in case of frequent collision in HashMap. It internally switches to a balanced tree from the 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 the 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 the 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 the 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.

LinkedHashMap is a trade-off between two, like HashMap it also provides constant-time performance for add, contains, and removes, though it's slightly slower than HashMap, to maintain a 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 an insertion order or access order, consider using LinkedHashMap over TreeMap in Java.

5. Thread-safety and Synchronization

All three Map implementation is not thread-safe, which means you can not use them safely in a multi-threaded application. Though you can synchronize them externally by using the 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 of 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.

6. Internal Implementation

TreeMap is a 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 are very popular in Java, for example, the 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 a linked list to provide an insertion order guarantee. It uses a 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 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, 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 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 below example.

LinkedHashMap, TreeMap, and HashMap Example 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 the reverse Comparator provided to it. Also, LinkedHashMap has created a copy of TreeMap, and the order of entries is retained.

Summary

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

That's all about the difference between LinkedHashMap, TreeMap, and HashMap in Java. Though all three are Map implementation, they have a different purpose and are used accordingly. Use LinkedHashMap, if you need to maintain insertion or access order of mappings like in LRU Cache.

Use TreeMap, if you need to maintain mappings in 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 requirements. HashMap allows you to retrieve an object in O(1) time if you know the key.


Other Java Collection interview questions you may like 

If you like this article and want to know more about other Collection classes, do check the following interview questions analysis and explanation from the 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)
• 50 Java Programs from Coding Interviews (list)
• 10 Java Garbage Collection Interview Questions (list)
• 21 Java Final modifier Interview Questions (list)
• 21 Java Inheritance Interview Questions with Answers (list)
• 10 Date, Time, and Calendar based Interview Questions with Answers (list)
• 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]
• Top 5 Courses to learn Java Collections Framework in-depth (courses)

Thanks for reading this article so far. If you like this article then please share it with your friends and colleagues. If you have any questions or feedback then please drop a comment.