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
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:
As we have seen various overloaded constructors of a TreeMap. Let’s see the performance factor of the TreeMap as the below:
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.
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:
Let’s see the following use of the compareTo() method:
As we have discussed, TreeMap is working based on the 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:
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.
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,
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.
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:
Hope this article is able to give much information about the internal working of TreeMap in Java.
Happy Learning with DineshonJava.
Strategy Design Patterns We can easily create a strategy design pattern using lambda. To implement…
Decorator Pattern A decorator pattern allows a user to add new functionality to an existing…
Delegating pattern In software engineering, the delegation pattern is an object-oriented design pattern that allows…
Technology has emerged a lot in the last decade, and now we have artificial intelligence;…
Managing a database is becoming increasingly complex now due to the vast amount of data…
Overview In this article, we will explore Spring Scheduler how we could use it by…