TreeMap

PreviousMaps NextAutoboxing And Unboxing

Last updated 6 years ago

Was this helpful?

TreeMap

Java TreeMap is a based implementation of Java’s Map interface.

The entries in a TreeMap are always sorted based on the natural ordering of the keys, or based on a custom that you can provide at the time of creation of the TreeMap.

The TreeMap class is part of Java’s collection framework. It implements the NavigableMap interface, which in turn extends the SortedMap interface. Following is the class hierarchy of TreeMap -

The interface provides functionalities to maintain the ordering of keys. And the interface provides functionalities to navigate through the map. For example, finding the entry just greater than or just less than the given key, finding the first and last entry in the TreeMap etc.

Since a TreeMap implements NavigableMap interface, it has the functionalities of both the NavigableMap as well as the SortedMap.

Following are few key points to note about TreeMap in Java -

A TreeMap is always sorted based on keys. The sorting order follows the natural ordering of keys. You may also provide a custom to the TreeMap at the time of creation to let it sort the keys using the supplied Comparator.
A TreeMap cannot contain duplicate keys.
TreeMap cannot contain the null key. However, It can have null values.
TreeMap is not synchronized. Access to TreeMaps must be synchronized explicitly in a multi-threaded environment.

Creating a TreeMap

1. Simple TreeMap

This example shows how to create a simple TreeMap and add new key-value pairs to it. The entries in the TreeMap will be sorted based on the natural ordering of keys -

import java.util.SortedMap;
import java.util.TreeMap;

public class CreateTreeMapExample {
    public static void main(String[] args) {
        // Creating a TreeMap
        SortedMap<String, String> fileExtensions  = new TreeMap<>();

        // Adding new key-value pairs to a TreeMap
        fileExtensions.put("python", ".py");
        fileExtensions.put("c++", ".cpp");
        fileExtensions.put("kotlin", ".kt");
        fileExtensions.put("golang", ".go");
        fileExtensions.put("java", ".java");

        // Printing the TreeMap (Output will be sorted based on keys)
        System.out.println(fileExtensions);
    }

}

# Output
{c++=.cpp, golang=.go, java=.java, kotlin=.kt, python=.py}

2. TreeMap with a custom Comparator (Descending Order)

This example demonstrates how to create a TreeMap with a custom comparator that orders the TreeMap entries in the descending order of keys -

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

public class CreateTreeMapCustomComparatorExample {
    public static void main(String[] args) {
        // Creating a TreeMap with a Custom comparator (Descending order)
        SortedMap<String, String> fileExtensions = new TreeMap<>(new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return s2.compareTo(s1);
            }
        });

        /*
            The above TreeMap with custom Comparator can be simply written as -
            SortedMap<String, String> fileExtensions = new TreeMap<>(Comparator.reverseOrder());
        */

        // Adding new key-value pairs to a TreeMap
        fileExtensions.put("python", ".py");
        fileExtensions.put("c++", ".cpp");
        fileExtensions.put("kotlin", ".kt");
        fileExtensions.put("golang", ".go");
        fileExtensions.put("java", ".java");

        // Printing the TreeMap (The keys will be sorted based on the supplied comparator)
        System.out.println(fileExtensions);

    }
}

# Output
{python=.py, kotlin=.kt, java=.java, golang=.go, c++=.cpp}

3. TreeMap with a custom Comparator (Case Insensitive Order)

The following example shows how to create a Case Insensitive Map by passing a custom CASE_INSENSITIVE_ORDER comparator to the TreeMap. The TreeMap will ignore case while ordering the keys.

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

public class CreateTreeMapCaseInsensitiveOrderExample {
    public static void main(String[] args) {
        // TreeMap with keys sorted by ignoring case
        SortedMap<String, String> fileExtensions = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);

        /*
            The above statement is the short form of -
            SortedMap<String, String> fileExtensions = new TreeMap<>(new Comparator<String>() {
                @Override
                public int compare(String s1, String s2) {
                    return s1.compareToIgnoreCase(s2);
                }
            });
        */

        fileExtensions.put("PYTHON", ".py");
        fileExtensions.put("c++", ".cpp");
        fileExtensions.put("KOTLIN", ".kt");
        fileExtensions.put("Golang", ".go");

        // The keys will be sorted ignoring the case (Try removing String.CASE_INSENSITIVE_ORDER and see the output)
        System.out.println(fileExtensions);
    }
}

# Output
{c++=.cpp, Golang=.go, KOTLIN=.kt, PYTHON=.py}

Accessing the entries of a TreeMap

The following example demonstrates how to -

Find the size of a TreeMap.
Check if a given key exists in a TreeMap.
Retrieve the first entry in the TreeMap.
Retrieve the last entry in the TreeMap.
Retrieve the entry whose key is just lower than the given key.
Retrieve the entry whose key is just higher than the given key.

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

public class AccessEntriesFromTreeMapExample {
    public static void main(String[] args) {
        TreeMap<Integer, String> employees = new TreeMap<>();

        employees.put(1003, "Rajeev");
        employees.put(1001, "James");
        employees.put(1002, "Sachin");
        employees.put(1004, "Chris");

        System.out.println("Employees map : " + employees);

        // Finding the size of a TreeMap
        System.out.println("Total number of employees : " + employees.size());

        // Check if a given key exists in a TreeMap
        Integer id = 1004;
        if(employees.containsKey(id)) {
            // Get the value associated with a given key in a TreeMap
            String name = employees.get(id);
            System.out.println("Employee with id " + id + " : " + name);
        } else {
            System.out.println("Employee does not exist with id : " + id);
        }

        // Find the first and last entry
        System.out.println("First entry in employees map : " + employees.firstEntry());
        System.out.println("Last entry in employees map : " + employees.lastEntry());

        // Find the entry whose key is just less than the given key
        Map.Entry<Integer, String> employeeJustBelow = employees.lowerEntry(1002);
        System.out.println("Employee just below id 1002 : " + employeeJustBelow);

        // Find the entry whose key is just higher than the given key
        Map.Entry<Integer, String> employeeJustAbove = employees.higherEntry(1002);
        System.out.println("Employee just above id 1002 : " + employeeJustAbove);
    }
}

# Output
Employees map : {1001=James, 1002=Sachin, 1003=Rajeev, 1004=Chris}
Total number of employees : 4
Employee with id 1004 : Chris
First entry in employees map : 1001=James
Last entry in employees map : 1004=Chris
Employee just below id 1002 : 1001=James
Employee just above id 1002 : 1003=Rajeev

Removing Entries from a TreeMap

The example below shows how to -

Remove a key from a TreeMap.
Remove a key from a TreeMap only if it is associated with a given value.
Remove the first entry of the TreeMap.
Remove the last entry of the TreeMap.

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

public class RemoveEntriesFromTreeMapExample {
    public static void main(String[] args) {
        TreeMap<String, String> countryISOCodeMapping = new TreeMap<>();

        countryISOCodeMapping.put("India", "IN");
        countryISOCodeMapping.put("United States of America", "US");
        countryISOCodeMapping.put("China", "CN");
        countryISOCodeMapping.put("United Kingdom", "UK");
        countryISOCodeMapping.put("Russia", "RU");
        countryISOCodeMapping.put("Japan", "JP");

        System.out.println("CountryISOCodeMapping : " + countryISOCodeMapping);

        // Remove the mapping for a given key
        String countryName = "Japan";
        String isoCode = countryISOCodeMapping.remove(countryName);
        if(isoCode != null) {
            System.out.println("Removed (" + countryName + " => " + isoCode + ") from the TreeMap. New TreeMap " + countryISOCodeMapping);
        } else {
            System.out.println(countryName + " does not exist, or it is mapped to a null value");
        }

        // Remove the mapping for the given key only if it is mapped to the given value
        countryName = "India";
        boolean isRemoved = countryISOCodeMapping.remove(countryName, "IA");
        System.out.println("Was the mapping removed for " + countryName + "? : " + isRemoved);

        // Remove the first entry from the TreeMap
        Map.Entry<String, String> firstEntry = countryISOCodeMapping.pollFirstEntry();
        System.out.println("Removed firstEntry : " + firstEntry + ", New TreeMap : " + countryISOCodeMapping);

        // Remove the last entry from the TreeMap
        Map.Entry<String, String> lastEntry = countryISOCodeMapping.pollLastEntry();
        System.out.println("Removed lastEntry : " + lastEntry + ", New TreeMap : " + countryISOCodeMapping);
    }
}

# Output
CountryISOCodeMapping : {China=CN, India=IN, Japan=JP, Russia=RU, United Kingdom=UK, United States of America=US}
Removed (Japan => JP) from the TreeMap. New TreeMap {China=CN, India=IN, Russia=RU, United Kingdom=UK, United States of America=US}
Was the mapping removed for India? : false
Removed firstEntry : China=CN, New TreeMap : {India=IN, Russia=RU, United Kingdom=UK, United States of America=US}
Removed lastEntry : United States of America=US, New TreeMap : {India=IN, Russia=RU, United Kingdom=UK}

Problems:

PreviousMaps NextAutoboxing And Unboxing

Last updated 6 years ago

Was this helpful?