SortedMap, NavigableMap, TreeMap in Java

Java Functions And Methods

Java Foundation

Java Flow Control

Java Inner Classes

Java 8 Features

Java File I/o

Java Multithreading

Java Arrays And Strings

Java Exception Handling

Java Classes

Java OOP's

Java Collections Framework

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.

Method	Description
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

​x
 
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}    }}

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.

Method	Description
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

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());     }}

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

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

Code Example

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());             }}

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

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`

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

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

SortedMap

NavigableMap Interface

Key Characteristics of NavigableMap:

TreeMap

Overview of TreeMap

Key Features of TreeMap

Key Differences between SortedMap and NavigableMap

Practical Use Cases

Key Differences between TreeMap and HashMap

Java Tutorial

Python Tutorial