Overview:
SortedMap
is a subinterface of Map
.Comparable
) or by a custom Comparator
provided at map creation.TreeMap
in Java.Method | Description |
---|---|
Comparator < ? super K > comparator() | Returns the comparator used for ordering the keys in this map, or
|
K firstKey() | Returns the first (smallest) key in the map.
|
K lastKey() | Returns the last (largest) key in the map.
|
SortedMap<K, V> headMap(K toKey): | Returns a view of the map containing all keys less than the specified
|
SortedMap<K, V> tailMap(K fromKey) | Returns a view of the map containing all keys greater than or equal to the specified
|
SortedMap<K, V> subMap(K fromKey, K toKey) | Returns a view of the map containing all keys between the specified
|
import java.util.SortedMap;
import java.util.TreeMap;
public class SortedMapExample {
public static void main(String[] args) {
SortedMap<String, Integer> sortedMap = new TreeMap<>();
sortedMap.put("apple", 1);
sortedMap.put("banana", 2);
sortedMap.put("cherry", 3);
System.out.println("Original Map: " + sortedMap);
System.out.println("First Key: " + sortedMap.firstKey()); // apple
System.out.println("Last Key: " + sortedMap.lastKey()); // cherry
System.out.println("Head Map (to 'cherry'): " + sortedMap.headMap("cherry"));
// {apple=1, banana=2}
System.out.println("Tail Map (from 'banana'): " + sortedMap.tailMap("banana"));
// {banana=2, cherry=3}
System.out.println("Sub Map (from 'apple' to 'cherry'): " +
sortedMap.subMap("apple", "cherry"));
// {apple=1, banana=2}
}
}
Original Map: {apple=1, banana=2, cherry=3}
First Key: apple
Last Key: cherry
Head Map (to 'cherry'): {apple=1, banana=2}
Tail Map (from 'banana'): {banana=2, cherry=3}
Sub Map (from 'apple' to 'cherry'): {apple=1, banana=2}
Overview:
NavigableMap
is a subinterface of SortedMap
.SortedMap
by adding methods for retrieving entries based on closest matches.Method | Description |
---|---|
Map.Entry<K, V> ceilingEntry(K key) | Returns the entry with the smallest key greater than or equal to the specified
|
Map.Entry<K, V> floorEntry(K key) | Returns the entry with the largest key less than or equal to the specified
|
K floorKey(K key) | Returns the largest key less than or equal to the specified key , or null if no such key exists. |
Map.Entry<K, V> higherEntry(K key) | Returns the entry with the smallest key strictly greater than the specified key , or null if no such entry exists. |
K higherKey(K key): | Returns the smallest key strictly greater than the specified key , or null if no such key exists. |
Map.Entry<K, V> lowerEntry(K key) | Returns the entry with the largest key strictly less than the specified key , or null if no such entry exists. |
K lowerKey(K key): | Returns the largest key strictly less than the specified key , or null if no such key exists. |
Map.Entry<K, V> pollFirstEntry() | Retrieves and removes the first (lowest) entry in the map, or returns null if the map is empty. |
Map.Entry<K, V> pollLastEntry(): | Retrieves and removes the last (highest) entry in the map, or returns null if the map is empty. |
NavigableMap<K, V> descendingMap(): | Returns a reversed order view of the map. |
NavigableSet<K> descendingKeySet(): | Returns a descending order set of the keys. |
xxxxxxxxxx
import java.util.NavigableMap;
import java.util.TreeMap;
import java.util.Map;
public class NavigableMapExample {
public static void main(String[] args) {
NavigableMap<String, Integer> navMap = new TreeMap<>();
navMap.put("apple", 1);
navMap.put("banana", 2);
navMap.put("cherry", 3);
System.out.println("Original Map: " + navMap);
// Closest matches
System.out.println("Ceiling Entry (banana): " + navMap.ceilingEntry("banana"));
System.out.println("Floor Entry (banana): " + navMap.floorEntry("banana"));
System.out.println("Higher Entry (banana): " + navMap.higherEntry("banana"));
System.out.println("Lower Entry (banana): " + navMap.lowerEntry("banana"));
// Removing entries
System.out.println("Poll First Entry: " + navMap.pollFirstEntry());
System.out.println("Poll Last Entry: " + navMap.pollLastEntry());
System.out.println("Map after polling: " + navMap);
// Descending Map
navMap.put("apple", 1);
navMap.put("cherry", 3);
System.out.println("Descending Map: " + navMap.descendingMap());
}
}
Original Map: {apple=1, banana=2, cherry=3}
Ceiling Entry (banana): banana=2
Floor Entry (banana): banana=2
Higher Entry (banana): cherry=3
Lower Entry (banana): apple=1
Poll First Entry: apple=1
Poll Last Entry: cherry=3
Map after polling: {banana=2}
Descending Map: {cherry=3, banana=2, apple=1}
The TreeMap
class in Java is part of the Java Collections Framework and is a concrete implementation of the NavigableMap
and SortedMap
interfaces. It maintains its entries in a sorted order based on the natural ordering of keys or by a specified comparator. Here’s an in-depth explanation of TreeMap
.
TreeMap
is a Map
implementation that stores key-value pairs in a sorted order.TreeMap
does not allow null keys (as opposed to HashMap
), but it allows multiple null values.java.util
package.TreeMap
supports all the navigable operations, like finding closest matches, head/tail views, etc.null
keys, which is a key difference from HashMap
.xxxxxxxxxx
import java.util.*;
public class TreeMapExample {
public static void main(String[] args) {
TreeMap<Integer, String> treeMap = new TreeMap<>();
// Adding key-value pairs to TreeMap
treeMap.put(3, "Three");
treeMap.put(1, "One");
treeMap.put(4, "Four");
treeMap.put(2, "Two");
System.out.println("TreeMap: " + treeMap);
// Output: TreeMap: {1=One, 2=Two, 3=Three, 4=Four}
// Accessing elements
System.out.println("First Key: " + treeMap.firstKey()); // Output: 1
System.out.println("Last Key: " + treeMap.lastKey()); // Output: 4
// Using headMap, tailMap, and subMap
System.out.println("Head Map (up to 3): " + treeMap.headMap(3));
System.out.println("Tail Map (from 2): " + treeMap.tailMap(2));
System.out.println("Sub Map (1 to 4): " + treeMap.subMap(1, 4));
// NavigableMap methods
System.out.println("Lower Key (3): " + treeMap.lowerKey(3)); // Output: 2
System.out.println("Floor Key (3): " + treeMap.floorKey(3)); // Output: 3
System.out.println("Ceiling Key (3): " + treeMap.ceilingKey(3)); // Output: 3
System.out.println("Higher Key (3): " + treeMap.higherKey(3)); // Output: 4
// Polling first and last entries
System.out.println("Poll First Entry: " + treeMap.pollFirstEntry()); // Output: 1=One
System.out.println("Poll Last Entry: " + treeMap.pollLastEntry()); // Output: 4=Four
// After polling entries
System.out.println("TreeMap after polling: " + treeMap);
// Descending Map
System.out.println("Descending Map: " + treeMap.descendingMap());
}
}
TreeMap: {1=One, 2=Two, 3=Three, 4=Four}
First Key: 1
Last Key: 4
Head Map (up to 3): {1=One, 2=Two}
Tail Map (from 2): {2=Two, 3=Three, 4=Four}
Sub Map (1 to 4): {1=One, 2=Two, 3=Three}
Lower Key (3): 2
Floor Key (3): 3
Ceiling Key (3): 3
Higher Key (3): 4
Poll First Entry: 1=One
Poll Last Entry: 4=Four
TreeMap after polling: {2=Two, 3=Three}
Descending Map: {3=Three, 2=Two}
Feature | SortedMap | NavigableMap |
---|---|---|
Ordering | Maintains keys in sorted (ascending) order | Maintains sorted order with additional navigation methods |
Closest Matches | Not available | Provides methods like lowerKey , floorKey , etc. to find closest matches |
Reverse Order View | Not available | Can create a descending view with descendingMap |
Additional Methods | Basic sorted submap methods | Enhanced navigation and retrieval methods like pollFirstEntry |
Feature | TreeMap | HashMap |
Ordering | Maintains sorted order of keys | No ordering (random) |
Null Keys | Does not allow null keys | Allows one null key |
Internal Structure | Red-Black Tree | Hash Table |
Performance | O(log n) for put , get , remove | O(1) for put , get , remove |
Use Case | When sorted order is required | When quick access without order is needed |