Algorithms

Internal Working of TreeMap in Java

This is another very frequently asked Java Developer Interview Questions of Internal Working of TreeMap in Java. How TreeMap works and what is an internal implementation of TreeMap. In our previous articles, we have already discussed other popular java interview questions such as the internal working of HashMap and internal working of LinkedHashMap. Also, we have discussed, what is the difference between HashMap and TreeMap. In this article, we will discuss the Internal Working of TreeMap in Java.

LinkedList Algorithms Interview Questions

Find and Break a Loop in a Linked list
How to Detect loop in a linked list
Find the nth node from the end of a singly linked list
Find the middle element in a linked list
How to Reverse linked list in Java
Delete given node from a singly linked list
Remove Duplicates from the Unsorted Singly Linked list
The singly linked list is palindrome without extra space

TreeMap in Java

The TreeMap is used to implement Map interface and NavigableMap along with the Abstract Class. TreeMap does not use hashing for storing key unlike the HashMap and LinkedHashMap use hashing for storing the key. HashMap and LinkedHashMap use array data structure to store nodes but the TreeMap uses a data structure called Red-Black tree. Also, all its elements store in the TreeMap are sorted by key. TreeMap performs sorting in natural order on its key, it also allows you to use Comparator for custom sorting implementation. We can provide Comparator at map creation time, depending on which constructor is used. Let’s see the following:

  • TreeMap(): This default constructor constructs an empty TreeMap that will be sorted by using the natural order of its keys.
  • TreeMap(Comparator comp): This is an argument constructor and it takes Comparator object to constructs an empty tree-based map. It will be sorted by using the Comparator comp.
  • TreeMap(Map map): It creates a TreeMap with the entries from a map, which will be sorted by using the natural order of the keys.
  • TreeMap(SortedMap sortedMap): It also initializes a TreeMap with the entries from sortedMap, which will be sorted in the same order as sortedMap.

As we have seen various overloaded constructors of a TreeMap. Let’s see the performance factor of the TreeMap as the below:

Performance of TreeMap

Performance wise TreeMap is slow if you will compare with HashMap and LinkedHashMap. The TreeMap provides guaranteed log(n) time complexity for the methods such as containsKey(), get(), put() and remove().

Also, a TreeMap is fail-fast in nature that means it is not synchronized and that is why is not thread-safe. You can make it thread-safe for multithreaded environments as the following:

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

Let’s discuss the internal structure of a TreeMap.

Internal Structure of TreeMap

TreeMap is based on tree data structure as its name suggested. As we know that, in a tree, each node has three references its parent, right and left element. Let’s see the following diagram:


As you can see in the above diagram, there are three references in the node such as a parent, right and left element with the following properties:

  1. The left element will always be logically less than the parent element.
  2. The right element will always be logically greater than OR equal to a parent element
  3. The logical comparison of Objects is done by natural order i.e. those object who implement Comparable interface and override compareTo(Object obj) method. Based on the return value,

Let’s see the following use of the compareTo() method:

  • If obj1.compareTo(obj2) returns a negative number, then obj1 is logically less than obj2.
  • If obj1.compareTo(obj2) returns positive number then obj1 is logically greater than obj2
  • If obj1.compareTo(obj2) returns zero, then obj1 is equal to obj2.

As we have discussed, TreeMap is working based on the Red-Black tree.

Red Black tree

In this article, I am not going to explain the Red Black algorithm in details, let’s see the pseudo code of Red Black algorithm in order to understand the internal implementation like the following:

  • As the name of the algorithm suggests, a colour of every node in the tree is either red or black.
  • Root node must be Black in color.
  • A red node can not have a red colour neighbor node.
  • All paths from a root node to the null should consist the same number of black nodes.

Internal Working of TreeMap in Java

Now, we will discuss an example and see how does TreeMap work internally.

/**
 * 
 */
package com.dineshonjava.algo.map;

import java.util.Map;
import java.util.TreeMap;

/**
 * @author Dinesh.Rajput
 *
 */
public class TreeMapTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Map<Key, String> treemap = new TreeMap<>();
                treemap.put(new Key("Anamika"), "Anamika");
		treemap.put(new Key("Rushika"), "Rushika");
		treemap.put(new Key("Dinesh"), "Dinesh");
		treemap.put(new Key("Arnav"), "Arnav");
	}

}

Let’s see Key class:

/**
 * 
 */
package com.dineshonjava.algo.map;

/**
 * @author Dinesh.Rajput
 *
 */
public class Key implements Comparable{
	
	final int data = 112;
	private String key;
	
	public Key(String key) {
		super();
		this.key = key;
	}
	
	@Override
	public int compareTo(Key obj) {
		return key.compareTo(obj.key);
	}
	
}

As you can see in the above Key class, I didn’t implement hashCode() and equals() method becuase TreeMap does not use hashing.

Let’s understand step by step.

Step 1: Initially when we create a TreeMap object as

Map<Key, String> treemap = new TreeMap<>();

There are no elements in it. Let’s add the first element on it.

Step 2: Adding the first element into TreeMap

treemap.put(new Key("Anamika"), "Anamika");

So {“Anamika”} is the first key object being inserted as key. This element will be root node for tree and structure for TreeMap becomes as below.

Step 3: Adding the second element into TreeMap

treemap.put(new Key("Rushika"), "Rushika");

Now, {“Rushika”} is logically greater than {“Anamika”} and hence according to our rules,

  • {“Rushika”} will be placed to the right of {“Anamika”}.
  • {“Anamika”} will be a parent of {“Rushika”}.

After inserting this element, the structure for TreeMap becomes as below.

Step 4: Adding third element into TreeMap

treemap.put(new Key("Dinesh"), "Dinesh");

So {“Dinesh”} is the first key object being inserted as key. This element will be root node for tree and structure for TreeMap becomes as below.

As you can see in the above diagram, this element {“Dinesh”} is the root node for a tree. As we have discussed above properties and rules of the Red-Black tree, the Red-Black tree implementation will give us sorted order from left to right. So according to diagram elements of a tree become as below.

  • {“Anamika”} will be to the left of {“Dinesh”}
  • {“Rushika”} will be to the right of {“Dinesh”}

Step 5: Adding the third element into TreeMap

treemap.put(new Key("Arnav"), "Arnav");

So {“Arnav”} is the first key object being inserted as key. After adding this element, a structure for TreeMap becomes as below.

As you can see in the above diagram of the TreeMap, all elements are as below:

  • {“Anamika”} will be to the left of {“Dinesh”}
  • {“Arnav”} will be to right of {“Dinesh”}
  • {“Rushika”} will be to right of {“Anamika”}

Hope this article is able to give much information about the internal working of TreeMap in Java.

Happy Learning with DineshonJava.

Previous
Next
Dinesh Rajput

Dinesh Rajput is the chief editor of a website Dineshonjava, a technical blog dedicated to the Spring and Java technologies. It has a series of articles related to Java technologies. Dinesh has been a Spring enthusiast since 2008 and is a Pivotal Certified Spring Professional, an author of a book Spring 5 Design Pattern, and a blogger. He has more than 10 years of experience with different aspects of Spring and Java design and development. His core expertise lies in the latest version of Spring Framework, Spring Boot, Spring Security, creating REST APIs, Microservice Architecture, Reactive Pattern, Spring AOP, Design Patterns, Struts, Hibernate, Web Services, Spring Batch, Cassandra, MongoDB, and Web Application Design and Architecture. He is currently working as a technology manager at a leading product and web development company. He worked as a developer and tech lead at the Bennett, Coleman & Co. Ltd and was the first developer in his previous company, Paytm. Dinesh is passionate about the latest Java technologies and loves to write technical blogs related to it. He is a very active member of the Java and Spring community on different forums. When it comes to the Spring Framework and Java, Dinesh tops the list!

Share
Published by
Dinesh Rajput

Recent Posts

Strategy Design Patterns using Lambda

Strategy Design Patterns We can easily create a strategy design pattern using lambda. To implement…

2 years ago

Decorator Pattern using Lambda

Decorator Pattern A decorator pattern allows a user to add new functionality to an existing…

2 years ago

Delegating pattern using lambda

Delegating pattern In software engineering, the delegation pattern is an object-oriented design pattern that allows…

2 years ago

Spring Vs Django- Know The Difference Between The Two

Technology has emerged a lot in the last decade, and now we have artificial intelligence;…

2 years ago

TOP 20 MongoDB INTERVIEW QUESTIONS 2022

Managing a database is becoming increasingly complex now due to the vast amount of data…

2 years ago

Scheduler @Scheduled Annotation Spring Boot

Overview In this article, we will explore Spring Scheduler how we could use it by…

3 years ago