SortedMap

Overview:

  • SortedMap is a subinterface of Map.
  • It maintains the keys in a sorted order, either by natural ordering (if the keys implement Comparable) or by a custom Comparator provided at map creation.
  • Commonly used when you need a map with keys in ascending order.
  • This interface is implemented by TreeMap in Java.
  • Since it maintains the sorted order, duplicate keys are not allowed, but duplicate values are.
MethodDescription
Comparator < ? super K > comparator()

Returns the comparator used for ordering the keys in this map, or null if natural ordering is used.

SortedMap<String, Integer> map = new TreeMap<>();
Comparator<? super String> comp = map.comparator();  
// Returns null for natural ordering
K firstKey()

Returns the first (smallest) key in the map.

map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);
System.out.println(map.firstKey());  // Output: apple
K lastKey()

Returns the last (largest) key in the map.

System.out.println(map.lastKey());  
// Output: cherry
SortedMap<K, V> headMap(K toKey):

Returns a view of the map containing all keys less than the specified toKey.

SortedMap<String, Integer> headMap = map.headMap("cherry");
System.out.println(headMap);  // Output: {apple=1, banana=2}
SortedMap<K, V> tailMap(K fromKey)

Returns a view of the map containing all keys greater than or equal to the specified fromKey.

SortedMap<String, Integer> tailMap = map.tailMap("banana");
System.out.println(tailMap);  
// Output: {banana=2, cherry=3}
SortedMap<K, V> subMap(K fromKey, K toKey)

Returns a view of the map containing all keys between the specified fromKey (inclusive) and toKey (exclusive).

SortedMap<String, Integer> subMap = map.subMap("apple", "cherry");
System.out.println(subMap);  // Output: {apple=1, banana=2}
Code Example
Output
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}

NavigableMap Interface

Overview:

  • NavigableMap is a subinterface of SortedMap.
  • It adds methods for navigating the map in ascending or descending order.
  • It provides methods to retrieve the closest matches for a key, allowing for finer control over navigation.

Key Characteristics of NavigableMap:

  • It builds on SortedMap by adding methods for retrieving entries based on closest matches.
  • Supports descending order and removal of entries based on the closest matching key.
MethodDescription
Map.Entry<K, V> ceilingEntry(K key)

Returns the entry with the smallest key greater than or equal to the specified key, or null if no such entry exists.

map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);
Map.Entry<String, Integer> entry = map.ceilingEntry("banana");
System.out.println(entry);  // Output: banana=2
Map.Entry<K, V> floorEntry(K key)

Returns the entry with the largest key less than or equal to the specified key, or null if no such entry exists.

Map.Entry<String, Integer> entry = map.floorEntry("banana");
System.out.println(entry);  // Output: banana=2
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.
Code Example
Output
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}

TreeMap

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.

Overview of TreeMap

  • TreeMap is a Map implementation that stores key-value pairs in a sorted order.
  • It uses a Red-Black tree under the hood, which is a self-balancing binary search tree.
  • The keys are sorted in ascending order by default.
  • TreeMap does not allow null keys (as opposed to HashMap), but it allows multiple null values.
  • It’s part of the java.util package.

Key Features of TreeMap

  1. Sorted Order: Keys are automatically sorted in ascending order.
  2. Navigable Operations: TreeMap supports all the navigable operations, like finding closest matches, head/tail views, etc.
  3. Self-Balancing Tree: Internally, it uses a Red-Black Tree structure to maintain balance and enable efficient search operations.
  4. No Null Keys: It doesn’t allow null keys, which is a key difference from HashMap.
Code Example
Output
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}

Key Differences between SortedMap and NavigableMap

FeatureSortedMapNavigableMap
OrderingMaintains keys in sorted (ascending) orderMaintains sorted order with additional navigation methods
Closest MatchesNot availableProvides methods like lowerKey, floorKey, etc. to find closest matches
Reverse Order ViewNot availableCan create a descending view with descendingMap
Additional MethodsBasic sorted submap methodsEnhanced navigation and retrieval methods like pollFirstEntry

Practical Use Cases

  • SortedMap: Use when you need a map with keys in a sorted order, typically for scenarios like range-based retrievals (submaps).
  • NavigableMap: Ideal for applications requiring fine-grained control over key access, like implementing interval trees or caching systems with nearest-match queries.

Key Differences between TreeMap and HashMap

FeatureTreeMapHashMap
OrderingMaintains sorted order of keysNo ordering (random)
Null KeysDoes not allow null keysAllows one null key
Internal StructureRed-Black TreeHash Table
PerformanceO(log n) for put, get, removeO(1) for put, get, remove
Use CaseWhen sorted order is requiredWhen quick access without order is needed