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

SortedMap	NavigableMap
Provides a total ordering on its keys.	Extends the ordering capabilities to allow for explicit navigation.
Offers basic operations like firstKey(), lastKey(), headMap(), tailMap(), and subMap().	Includes methods like lowerKey(), floorKey(), ceilingKey(), higherKey(), pollFirstEntry(), and pollLastEntry().
Does not provide navigation methods to find keys and entries relative to a specified target.	Allows for finding the closest matches for given search targets.

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.