JAVA COLLECTION INTERVIEW QUESTIONS

Internal Working Of TreeMap in Java Collection Framework

A complete guide for understanding TreeMap and its internal working.

The red-black tree that is internally used for TreeMap

Learning Java is fun when you understand the internal working mechanism of the classes that you use to write your applications. One of the core classes that I have already covered is HashMap. This article is a continuation of that and we’ll deep dive into what, why, and how of the TreeMap class.

What Is TreeMap?

TreeMap is a Red-Black tree-based map implementation. The map is sorted according to the natural ordering of its keys (for Integer as key natural order is ascending order, for String as key natural order is alphabetical order), or by a Comparator provided at map creation time, depending on which constructor is used.

This implementation of TreeMap provides guaranteed log(n) time cost for the containsKey, get, put and removeoperations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest’s Introduction to Algorithms.

TreeMap class that extends AbstractMap and implements NavigableMap.

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

TreeMap is defined in java.util Package.

TreeMap Default Sorting:

Let’s create a basic TreeMap and add some items to it and see how it stores them.

import java.util.TreeMap;

public class TestTreeMap {

    public static void main(String[] args) {
        TreeMap<Integer, String> studentBranch = new TreeMap<Integer, String>();
        studentBranch.put(101, "Computer");
        studentBranch.put(105, "Mechanical");
        studentBranch.put(102, "Electrical");
        studentBranch.put(103, "Chemical");
        studentBranch.put(104, "Civil");

        System.out.println("Student Ids : " + studentBranch.keySet());
    }
}

Output:

Student Ids : [101, 102, 103, 104, 105]

In this example, we added 5 items to the TreeMap in a non-orderly manner. But when we tried to retrieve the keys from the Map we can see they are returned in an ordered manner on keys. Note that keys are Integers and hence default sorting order is ascending.

Similar logic is applied to String keys. They are sorted and stored in alphabetic order.

import java.util.TreeMap;

public class TestTreeMap {

    public static void main(String[] args) {
        TreeMap<String, Integer> groceryItems = new TreeMap<String, Integer>();
        groceryItems.put("Maggie", 2);
        groceryItems.put("Chocolate", 5);
        groceryItems.put("Salt", 1);
        groceryItems.put("Sugar", 3);
        groceryItems.put("Biscuit", 4);

        System.out.println("Groceries Items : " + groceryItems.keySet());
    }
}

Output:

Groceries Items : [Biscuit, Chocolate, Maggie, Salt, Sugar]

Reverse Sorting in TreeMap:

A HashMap does not guarantee the order of keys stored in the map but TreeMap guarantees that the keys will always be stored in sorted order as per the order specified while creating TreeMap.

import java.util.Comparator;
import java.util.TreeMap;

public class TestTreeMap {

    public static void main(String[] args) {
        TreeMap<String, Integer> groceryItems = new TreeMap<String, Integer>(Comparator.<String>reverseOrder());
        groceryItems.put("Maggie", 2);
        groceryItems.put("Chocolate", 5);
        groceryItems.put("Salt", 1);
        groceryItems.put("Sugar", 3);
        groceryItems.put("Biscuit", 4);

        System.out.println("Groceries Items : " + groceryItems.keySet());
    }
}

Output:

Groceries Items : [Sugar, Salt, Maggie, Chocolate, Biscuit]

In the above example, entries are stored in TreeMap based on the reversed order of the keys.

Why Do We Need TreeMap?

There are multiple reasons why we need TreeMap.

• As the entries are stored in the map in sorted order, we can get the first and last entries very easily.
• Many inbuilt functions can be used to get part of the map.

import java.util.Comparator;
import java.util.TreeMap;

public class TestTreeMap {

    public static void main(String[] args) {
        TreeMap<String, Integer> groceryItems =
                new TreeMap<String, Integer>(Comparator.<String>naturalOrder());
        groceryItems.put("Maggie", 2);
        groceryItems.put("Chocolate", 5);
        groceryItems.put("Salt", 1);
        groceryItems.put("Sugar", 3);
        groceryItems.put("Biscuit", 4);

        System.out.println("First Entry : " + groceryItems.firstEntry());
        System.out.println("Last Entry : " + groceryItems.lastEntry());
        System.out.println("First Key : " + groceryItems.firstKey());
        System.out.println("First Key : " + groceryItems.lastKey());

        System.out.println("Map content : " + groceryItems.entrySet());
        System.out.println("First 3 Entries : " +
                groceryItems.headMap("Salt").entrySet());

    }
}

Output :

First Entry : Biscuit=4
Last Entry : Sugar=3
First Key : Biscuit
First Key : Sugar
Map content : [Biscuit=4, Chocolate=5, Maggie=2, Salt=1, Sugar=3]
First 3 Entries : [Biscuit=4, Chocolate=5, Maggie=2]

How Does TreeMap Work?

Internally TreeMap uses RedBlack Tree which is a self-balancing BST. In the case of the red-black tree the operations like search, get, put and remove are performed in O(log n) because the max length of any branch is log n .

In the worst-case scenario, the max length of any branch of the RedBlack tree can be log(n) as opposed to the BST where there can be a skewed branch of length n. Hence worst case time complexity of TreeMap is O(log(n)).

You may refer to the Introduction to Algorithms by CLR for a detailed understanding of the RedBlack Tree Data Structure.

Note if we think to use TreeMap in a multi-threaded environment:

• Note that this implementation is not synchronized. If multiple threads access a map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with an existing key is not a structural modification.)
• This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be “wrapped” using the Collections.synchronizedSortedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:
  SortedMap m = Collections.synchronizedSortedMap(new TreeMap(…));
• The iterators returned by the iterator method of the collections returned by all of this class’s “collection view methods” are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator’s remove method, the iterator will throw a ConcurrentModificationException.
• Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

That’s all for this article. Hope you enjoyed it.

You Can Follow Vikram Gupta For Similar Content.

1. Comparing ArrayList and LinkedList in Java

Comparing ArrayList and LinkedList in Java

2. Internal Working of HashMap in Java

Internal Working of HashMap in Java

3. Comparing HashMap and ConcurrentHashMap in Java

Comparing HashMap and ConcurrentHashMap in Java

4. Complete the Guide on LinkedHashMap in Java

Complete Guide on LinkedHashMap in Java

5. Internal Working Of TreeMap in Java Collection Framework

Internal Working Of TreeMap in Java Collection Framework

6. Internal Working of HashSet in Java

Internal Working of HashSet in Java