Treemap vs Hashmap vs Linkedhashmap in Java

Last Updated on July 1, 2022 by Ria Pathak

While learning Java, you all must have come across these terms of TreeMap, hashmap, Linkedhashmaps also have used these data structures and their implementations in your programs. But what is the difference between these three implementations and when to use which one?

Well, in this brief blog on the differences between Treemap, Hashmap, and Linkedhashmap, we will take you through the most basic differences and give you an idea of their applications.

Introduction

Maps, as we know store key-value pairs, hence as we can comprehend each of Treemap, Hashmap, and Linkedhashmap stores the elements as key-value pairs by implementing the java.util.Map interface but the only difference comes into play when we observe their time complexities.

TreeMap: This kind of map stores elements in an ordered fashion of keys and when iterating you can iterate through the keys in sorted order only. This means the elements also implement their comparable interface by which they make the comparisons for sorting. Under the hood, TreeMap is implemented by Red-Black Trees, and hence their insertion and lookup time is O(logn).

• This map extends the AbstractMap class and implements the NavigableMap interface.
• Unique elements can be stored.
• Null keys cannot be stored but there can be multiple null values.

Syntax: public class TreeMap extends AbstractMap implements NavigableMap

HashMap: This kind of map stores elements in an arbitrary manner and the hood implementation is based on the array of linked lists. HashMap takes O(1) (constant) insertion and lookup times.

• HashMap also contains values based on keys
• Unique elements can be stored only.
• It may contain 1 null key and multiple null values
• No particular order is maintained.

Syntax: public class LinkedHashMap extends HashMap implements Map

LinkedHashMap: This kind of map stores elements in sorted order of their insertion and can be accessed in that order only. Under the hood, LinkedHashMap is a non-synchronized version of HashMap that implements the Map interface. This also supports insertion and lookup in O(1) i.e. constant time.

Syntax: public class LinkedHashMap extends HashMap implements Map

Let me explain this with a table format –

Difference between TreeMap HashMap & LinkedHashMap

Code Implementation –

Treemap

import java.util.*;  
class Main
{
    static void func(AbstractMap<Integer, String> map)
    { 
        int[] array= {1, 2, 5, 3,0};
        for (int x: array) 
        { 
            map.put(x, Integer.toString(x)); 
        } 
        for (int k: map.keySet())
        {
            System.out.print(k + " "); 
        }
    }   
    public static void main (String[] args)
    {
        TreeMap<Integer, String> map = new TreeMap<Integer, String>();
        func(map);
    }
}

Output: 0 1 2 3 5

Hashmap

import java.util.*;
class Main
{
	static void func(AbstractMap<Integer, String> map)
	{
		int[] array= {1, 2, 5, 0,3};
		for (int x: array)
		{
			map.put(x, Integer.toString(x));
		}
		for (int k: map.keySet())
		{
			System.out.print(k + " ");
		}
	}
	public static void main (String[] args)
	{
		HashMap<Integer, String> map = new HashMap<Integer, String>();
		func(map);
	}
}

Output: 0 1 2 3 5

Linkedhashmap

import java.util.*;
class Main
{
	static void func(AbstractMap<Integer, String> map)
	{
		int[] array= {1, 2, 0, 5,3};
		for (int x: array)
		{
			map.put(x, Integer.toString(x));
		}
		for (int k: map.keySet())
		{
			System.out.print(k + ", ");
		}
	}
	
	public static void main (String[] args)
	{
		LinkedHashMap<Integer, String> map = new LinkedHashMap<Integer, String>();
		func(map);
	}
}

Output: 0 1 2 3 5

This article tried to discuss the most important difference in the implementation and the time complexities of various operations of TreeMap, HashMap, and LinkedHashMap and gave a brief code implementation for all of them. Hope this blog helps you understand the differences between them. To learn more feel free to check Foundation Courses at Prepbytes