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
- Maintains sorted order of keys.
- Implements the SortedMap and NavigableMap interfaces.
- 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
- Keys must be Comparable or you must provide a
Comparatorduring construction. - Null keys are not allowed in
TreeMap, but null values are permitted. - Use TreeMap when you need sorted access; otherwise,
HashMapis a better choice for performance.