Treemap vs Hashmap vs Linkedhashmap in Java

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

Properties TreeMap HashMap LinkedHashMap
Order of Insertion Sorted order of keys Random order Sorted order of their insertion
Null keys Not allowed allowed allowed
Synchronization Non-synchronized Non-synchronized - can be synchronized also Non-synchronized
Interface SortedMap, NavigableMap Map Map
Applications Where navigable features are used Fast retrieval and concurrency control LRU cache

Code Implementation -

Treemap

import java.util.*;  
class Main
{
    static void func(AbstractMap 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 map = new TreeMap();
        func(map);
    }
}

Output: 0 1 2 3 5

Hashmap

import java.util.*;
class Main
{
	static void func(AbstractMap 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 map = new HashMap();
		func(map);
	}
}

Output: 0 1 2 3 5

Linkedhashmap

import java.util.*;
class Main
{
	static void func(AbstractMap 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 map = new LinkedHashMap();
		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 practice more problems you can check out MYCODE | Competitive Programming

Previous post Reverse a Doubly Linked List
Next post The most efficient way to Pairwise swap elements of a given linked list

Leave a Reply

Your email address will not be published. Required fields are marked *