Difference between HashMap, TreeMap, and LinkedHashMap in Java

This post will discuss the major difference between HashMap, TreeMap and LinkedHashMap classes in Java.

We know that a Map is an object that represents a mapping from unique keys to values. Java offers several useful implementations of the java.util.Map interface, such as HashMap, TreeMap and LinkedHashMap, which are more or less similar in functionality. This post provides an overview of some of the major differences between these implementations.

1. Implementation Details

The HashMap and LinkedHashMap classes implement the Map interface, whereas TreeMap implements the Map, NavigableMap, and SortedMap interface. A HashMap is implemented as a Hash table, a TreeMap is implemented as a Red-Black Tree, and LinkedHashMap is implemented as a doubly-linked list buckets in Java.

2. Iteration Order of mappings

We know that a map’s contents can be viewed as a set of keys, collection of values, or set of key-value mappings. The most important difference between the HashMap, TreeMap and LinkedHashMap class lies in the order in which their iterators return the map’s contents.

HashMap makes no guarantees on the iteration order of the map. Also, the addition and removal of any element might change its iteration order.
TreeMap, on the other hand, is iterated according to the natural ordering of its keys or according to the Comparator specified at the map’s creation time.
LinkedHashMap maintains a doubly-linked list through all of its entries. This linked list defines the iteration order, which is the order in which keys were inserted into the map.

Here’s a simple Java program to illustrate the iteration order of HashMap, TreeMap and LinkedHashMap.

import java.util.HashMap;

import java.util.LinkedHashMap;

import java.util.Map;

import java.util.TreeMap;

class Main

{

public static void main(String[] args)

{

Map<String, String> hm = new LinkedHashMap<>();

hm.put("USA", "Washington");

hm.put("United Kingdom", "London");

hm.put("India", "New Delhi");

System.out.println("LinkedHashMap : " + hm);

hm = new TreeMap<>(hm);

System.out.println("TreeMap : " + hm);

hm = new HashMap<>(hm);

System.out.println("HashMap : " + hm);

}

Download Run Code

Output:

LinkedHashMap : {USA=Washington, United Kingdom=London, India=New Delhi}
TreeMap : {India=New Delhi, USA=Washington, United Kingdom=London}
HashMap : {United Kingdom=London, USA=Washington, India=New Delhi}

3. Performance

Assuming the hash function disperses the elements properly among the buckets, HashMap and LinkedHashMap offers O(1) time performance for the basic operations such as get, put, containsKey, remove, etc., On the other hand, TreeMap guarantees O(log(n)) time cost for these operations.

Please note that due to the added expense of maintaining the doubly-linked list, LinkedHashMap‘s performance is slightly lower than that of HashMap. So if performance is an issue, HashMap is preferred.

Now coming to the space complexity, HashMap requires less memory than TreeMap and LinkedHashMap since it uses a hash table to store the mappings. LinkedHashMap has the extra overhead of a doubly-linked list, and TreeMap is implemented as a Red-black tree, which takes more memory.

4. Null values/keys

HashMap and LinkedHashMap permits null values and null key, whereas TreeMap permits only null values (not null keys) if the natural ordering of keys is used. It supports null keys only if its Comparator supports comparison on null keys.

Which Implementation to use?

Use HashMap when performance is critical, and the ordering of keys doesn’t matter.
Use TreeMap when keys need to be ordered using their natural ordering or by a Comparator.
Use LinkedHashMap if the insertion order of the keys should be preserved.

That’s all about the differences between HashMap, TreeMap, and LinkedHashMap in Java.