TreeMap in Java

Introduction

In the Java Collections Framework, a TreeMap is a powerful data structure that implements the NavigableMap interface and extends AbstractMap. Unlike a HashMap, which stores keys in a pseudo-random order based on their hash codes, a TreeMap stores its keys in a sorted and ascending order, according to their natural ordering or a custom Comparator provided at map creation time.

TreeMap is the go-to choice when you need a map that inherently keeps its keys sorted. It is implemented based on a Red-Black Tree, a self-balancing binary search tree.

Internal Mechanics: The Red-Black Tree

The underlying data structure of a TreeMap is a Red-Black Tree. A Red-Black tree has the following properties:

1. Every node is either red or black.
2. The root is always black.
3. Every leaf (NIL node) is black.
4. If a node is red, then both its children are black.
5. Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes.

Because it is a balanced tree, TreeMap guarantees O(log n) time cost for the containsKey, get, put, and remove operations. This makes it slightly slower than HashMap (which provides O(1) average time complexity) but incredibly useful when ordered traversal or range queries are required.

Creating and Initializing a TreeMap

1. Natural Ordering

By default, TreeMap uses the natural ordering of its keys. The keys must implement the Comparable interface.

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

public class TreeMapExample {
    public static void main(String[] args) {
        Map<Integer, String> employeeMap = new TreeMap<>();
        
        employeeMap.put(103, "Alice");
        employeeMap.put(101, "Bob");
        employeeMap.put(102, "Charlie");
        
        // The output will be sorted by the keys (101, 102, 103)
        for (Map.Entry<Integer, String> entry : employeeMap.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

2. Custom Ordering with Comparator

You can supply a Comparator to define a custom sort order.

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

public class CustomOrderExample {
    public static void main(String[] args) {
        // Sort in descending order
        TreeMap<String, Integer> scores = new TreeMap<>(Comparator.reverseOrder());
        
        scores.put("Alice", 90);
        scores.put("Bob", 85);
        scores.put("Charlie", 95);
        
        System.out.println(scores); 
        // Output: {Charlie=95, Bob=85, Alice=90} (Reverse alphabetical order of keys)
    }
}

Advanced Features of NavigableMap

Because TreeMap implements NavigableMap, it provides powerful methods for finding the closest matches for given search targets.

• firstEntry() / lastEntry(): Returns the entry with the lowest/highest key.
• lowerEntry(K key) / higherEntry(K key): Returns the entry with the greatest key strictly less than, or strictly greater than the given key.
• floorEntry(K key) / ceilingEntry(K key): Returns the entry with the greatest key less than or equal to, or least key greater than or equal to the given key.

TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "Ten");
map.put(20, "Twenty");
map.put(30, "Thirty");

System.out.println(map.higherEntry(15)); // 20 -> Twenty
System.out.println(map.lowerKey(30));    // 20
System.out.println(map.floorEntry(25));  // 20 -> Twenty
System.out.println(map.ceilingKey(25));  // 30

Thread Safety

TreeMap is not thread-safe. If multiple threads access a map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. You can wrap it using Collections.synchronizedSortedMap:

SortedMap<K, V> syncTreeMap = Collections.synchronizedSortedMap(new TreeMap<K, V>());

Alternatively, for concurrent applications requiring sorted map functionality, consider using ConcurrentSkipListMap.

Summary

• Data Structure: Red-Black Tree.
• Time Complexity: O(log n) for basic operations (put, get, remove, containsKey).
• Ordering: Keys are sorted either implicitly (Comparable) or explicitly (Comparator).
• Null Keys: Cannot contain null keys if using natural ordering, as it will throw a NullPointerException. It can contain multiple null values.