How to Use TreeMap for Sorted Key Access in Java

The TreeMap class in Java is part of the java.util package and provides an implementation of the Map interface that keeps its keys sorted in a natural order (according to ) or a custom order (defined by a Comparator, if provided during construction)Comparable. It’s commonly used when you need to access keys in sorted order efficiently.
Here’s a guide on how to use TreeMap for sorted key access in Java:

Key Features of TreeMap

1. Maintains sorted order of keys.
2. Implements the SortedMap and NavigableMap interfaces.
3. Operates based on a Red-Black Tree, ensuring efficient sorting and lookup (O(log n) for most operations).

Basic Usage

Follow these steps to use TreeMap for sorted key access:

1. Create a TreeMap

You can create a TreeMap object with or without a custom comparator.

import java.util.*;

public class TreeMapExample {
    public static void main(String[] args) {
        // Natural ordering (keys must implement Comparable)
        TreeMap<Integer, String> treeMap = new TreeMap<>();

        // Custom comparator (e.g., descending order)
        TreeMap<Integer, String> customTreeMap = new TreeMap<>(Comparator.reverseOrder());
    }
}

2. Add Key-Value Pairs

Adding elements to a TreeMap is straightforward, using the put() method.

treeMap.put(3, "Three");
treeMap.put(1, "One");
treeMap.put(2, "Two");

The elements will automatically be stored in ascending order of keys.

3. Iterate Over Sorted Entries

The entries in the TreeMap can be accessed in sorted order.

for (Map.Entry<Integer, String> entry : treeMap.entrySet()) {
    System.out.println(entry.getKey() + " -> " + entry.getValue());
}

Output:

1 -> One
2 -> Two
3 -> Three

4. Access Specific Portions of the Map

The TreeMap provides powerful methods to access subsets of keys and values:

• headMap(K toKey, boolean inclusive): Get keys less than a given key.
• tailMap(K fromKey, boolean inclusive): Get keys greater than a given key.
• subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive): Get keys in a given range.

Example:

System.out.println("Keys less than 3: " + treeMap.headMap(3).keySet());
System.out.println("Keys greater than or equal to 2: " + treeMap.tailMap(2).keySet());
System.out.println("Keys between 1 (inclusive) and 3 (exclusive): " 
                   + treeMap.subMap(1, true, 3, false).keySet());

Output:

Keys less than 3: [1, 2]
Keys greater than or equal to 2: [2, 3]
Keys between 1 (inclusive) and 3 (exclusive): [1, 2]

5. Use NavigableMap Methods

The TreeMap also implements the NavigableMap interface, offering methods for navigation:

• firstKey() / lastKey(): Get the smallest/largest key.
• lowerKey(key) / higherKey(key): Get the keys just below/above a given key.
• floorKey(key) / ceilingKey(key): Get keys less than/greater than or equal to the given key.

Example:

System.out.println("First key: " + treeMap.firstKey());
System.out.println("Last key: " + treeMap.lastKey());
System.out.println("Key just below 3: " + treeMap.lowerKey(3));
System.out.println("Key just above 2: " + treeMap.higherKey(2));

Output:

First key: 1
Last key: 3
Key just below 3: 2
Key just above 2: 3

6. Remove Items

You can remove specific entries using the remove(key) method.

treeMap.remove(2); // Removes the key "2"
System.out.println(treeMap);

Output:

{1=One, 3=Three}

Example: Full Program

package org.kodejava.util;

import java.util.*;

public class TreeMapExample {
    public static void main(String[] args) {
        // Create a TreeMap
        TreeMap<Integer, String> treeMap = new TreeMap<>();

        // Add elements
        treeMap.put(3, "Three");
        treeMap.put(1, "One");
        treeMap.put(2, "Two");

        // Iterate over TreeMap
        System.out.println("TreeMap in ascending order:");
        for (Map.Entry<Integer, String> entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }

        // Access portions of the map
        System.out.println("Keys less than 2: " + treeMap.headMap(2).keySet());
        System.out.println("Keys greater than or equal to 2: " + treeMap.tailMap(2).keySet());

        // Use NavigableMap methods
        System.out.println("First key: " + treeMap.firstKey());
        System.out.println("Last key: " + treeMap.lastKey());
    }
}

Output:

TreeMap in ascending order:
1 -> One
2 -> Two
3 -> Three
Keys less than 2: [1]
Keys greater than or equal to 2: [2, 3]
First key: 1
Last key: 3

Things to Remember

1. Keys must be Comparable or you must provide a Comparator during construction.
2. Null keys are not allowed in TreeMap, but null values are permitted.
3. Use TreeMap when you need sorted access; otherwise, HashMap is a better choice for performance.