NavigableMap vs SortedMap in Java

1. Introduction

Java Collections Framework includes interfaces for sorting and navigating through ordered collections. SortedMap and NavigableMap are two interfaces that deal with maps that maintain their entries in sorted order. SortedMap is the older interface that provides operations for range views and key-based retrieval. NavigableMap extends SortedMap to provide additional navigation capabilities.

2. Key Points

1. SortedMap is an interface that provides sorting of keys based on their natural order or by a comparator.

2. NavigableMap includes all the features of SortedMap and adds methods for closer navigation of keys, such as higher, lower, ceiling, and floor entries.

3. While both are sorted, NavigableMap allows for more precise control when searching for entries relative to a specific target.

4. TreeMap is a concrete implementation of both SortedMap and NavigableMap.

3. Differences

NavigableMap	SortedMap
Extends the SortedMap interface, adding navigation methods to more easily access entries.	A subinterface of Map that guarantees the keys are sorted according to their natural ordering or by a specified comparator.
Provides methods to retrieve closest matches for given keys (ceilingEntry, floorEntry, higherEntry, lowerEntry).	Provides a range view of the map (subMap, headMap, tailMap) but without the closest-match capabilities.
Supports retrieving and removing entries based on the closest-match methods (pollFirstEntry, pollLastEntry).	Lacks methods for retrieving and removing entries based on closest matches or explicit positions.
Allows navigation in reverse order through descendingMap(), which returns a map in the reverse order of its keys.	Does not support reverse order navigation directly through the interface.
It offers NavigableSet views of the keys on the map, which support additional navigation methods.	Offers Set views of the keys, but the set does not provide additional navigation capabilities inherent to NavigableSet.

4. Example

// Import the necessary classes
import java.util.TreeMap;
import java.util.NavigableMap;

public class MapComparison {
    public static void main(String[] args) {
        // Step 1: Create a TreeMap, which is a NavigableMap
        NavigableMap<Integer, String> navigableMap = new TreeMap<>();

        // Step 2: Add some entries to the TreeMap
        navigableMap.put(1, "One");
        navigableMap.put(2, "Two");
        navigableMap.put(3, "Three");

        // Step 3: Use NavigableMap methods to navigate the entries
        System.out.println("First Entry: " + navigableMap.firstEntry());
        System.out.println("Last Key: " + navigableMap.lastKey());
        System.out.println("Floor Entry (2): " + navigableMap.floorEntry(2));
        System.out.println("Lower Entry (2): " + navigableMap.lowerEntry(2));
        System.out.println("Ceiling Entry (2): " + navigableMap.ceilingEntry(2));
        System.out.println("Higher Entry (2): " + navigableMap.higherEntry(2));
    }
}

Output:

First Entry: 1=One
Last Key: 3
Floor Entry (2): 2=Two
Lower Entry (2): 1=One
Ceiling Entry (2): 2=Two
Higher Entry (2): 3=Three

Explanation:

1. A TreeMap, which implements NavigableMap, is instantiated.

2. Entries are added to the map.

3. Various NavigableMap methods are demonstrated to navigate the map, including obtaining the first and last entries, and finding entries relative to the key '2'.

5. When to use?

- Use SortedMap when you need to maintain keys in sorted order and perform range view operations.

- Choose NavigableMap when you need more advanced search operations to find specific entries, like the greatest key less than a given key or the smallest key greater than or equal to a given key.