Explain the concept of SortedMap and NavigableMap.

Table of Contents

• Introduction
• What is SortedMap?
  • Features of SortedMap:
  • Example: Using SortedMap
• What is NavigableMap?
  • Features of NavigableMap:
  • Example: Using NavigableMap
• Differences Between SortedMap and NavigableMap
• Practical Use Cases
• Conclusion

Introduction

In Java, the **Map** interface represents a collection of key-value pairs, and several subinterfaces of Map provide additional functionality for sorting and navigation. Two such subinterfaces are **SortedMap** and **NavigableMap**, which offer methods for managing keys in a sorted order and providing navigation between them.

In this guide, we will explain the key concepts of SortedMap and NavigableMap, highlighting their features and differences.

What is SortedMap?

**SortedMap** is a subinterface of the **Map** interface in Java that represents a map where the keys are sorted in a natural order or by a comparator provided at the time of map creation. It ensures that the keys are stored in a specific order, usually ascending or descending, depending on the sorting criteria.

Features of SortedMap:

• Sorted Key-Order: The keys in a SortedMap are always sorted. The sorting order is either natural ordering (if the keys are Comparable) or custom order (if a Comparator is provided).
• Methods for Sorting: The SortedMap interface provides several methods for navigating the sorted map, such as:
  • firstKey(): Returns the first (lowest) key.
  • lastKey(): Returns the last (highest) key.
  • headMap(K toKey): Returns a view of the portion of the map whose keys are less than toKey.
  • tailMap(K fromKey): Returns a view of the portion of the map whose keys are greater than or equal to fromKey.
  • subMap(K fromKey, K toKey): Returns a view of the portion of the map whose keys are between fromKey (inclusive) and toKey (exclusive).

Example: Using SortedMap

Output:

What is NavigableMap?

**NavigableMap** is an extension of the **SortedMap** interface that adds methods to perform navigation on the map. In addition to the basic sorting features provided by SortedMap, NavigableMap allows you to perform operations such as finding the ceiling, floor, and higher or lower keys, making it more flexible for advanced navigation.

Features of NavigableMap:

• Additional Navigation Methods: NavigableMap introduces several methods for navigating through the keys, such as:
  • ceilingKey(K key): Returns the least key greater than or equal to the given key.
  • floorKey(K key): Returns the greatest key less than or equal to the given key.
  • higherKey(K key): Returns the least key strictly greater than the given key.
  • lowerKey(K key): Returns the greatest key strictly less than the given key.
  • pollFirstEntry(): Removes and returns the first (lowest) entry.
  • pollLastEntry(): Removes and returns the last (highest) entry.
• Descending Map: You can also obtain a reverse order map using the descendingMap() method, which returns a view of the map with keys in descending order.

Example: Using NavigableMap

Output:

Differences Between SortedMap and NavigableMap

Feature	SortedMap	NavigableMap
Sorting	Keys are sorted in natural order or by a comparator.	Inherits from SortedMap, so keys are sorted, but adds navigation capabilities.
Key Navigation	Limited navigation options (e.g., firstKey(), lastKey()).	Additional navigation methods like ceilingKey(), higherKey(), pollFirstEntry(), etc.
Descending View	Not available directly.	descendingMap() method returns a map with keys in reverse order.
Common Implementations	TreeMap	TreeMap

Practical Use Cases

• SortedMap is useful when you need to maintain a map where the keys should always be sorted, but you don't require advanced navigation. For example, you may use a SortedMap to maintain configurations where keys are naturally ordered (e.g., alphabetically or numerically).
• NavigableMap is ideal when you need more advanced navigation through the keys, such as finding the ceiling, floor, or nearest key. It is helpful in cases like range queries, where you need to access the closest matching key to a given value.

Conclusion

Both **SortedMap** and **NavigableMap** extend the basic **Map** interface to provide enhanced sorting and navigation capabilities. While **SortedMap** offers basic sorting and submap views, **NavigableMap** adds powerful methods for key navigation, making it more versatile for advanced use cases like range searching or finding the nearest key.

When deciding between the two, consider whether you need the added navigation features of **NavigableMap** or if a simpler **SortedMap** will suffice for your requirements. In most cases, **TreeMap** is the common implementation for both, but **NavigableMap** provides additional functionality if you need fine-grained control over key traversal.