Java SortedMap Interface 

---

The SortedMap interface in Java extends the Map interface, offering additional functionality that allows for maintaining the keys in a sorted order. It is a subtype of Map that guarantees that the keys will be sorted according to their natural order or based on a custom comparator.

Implementing classes like TreeMap provide an actual working model of a SortedMap, but SortedMap itself only defines methods for dealing with sorted key-value pairs. In this article, we will explore the SortedMap interface, its core methods, how it differs from other map implementations like HashMap, and practical examples of its usage.

---

What is SortedMap in Java?

The SortedMap interface is part of the java.util package and extends the Map interface. It defines a map where the keys are ordered based on their natural ordering or by a comparator provided at map creation time.

Key features of SortedMap:

• Key Sorting: The keys are automatically sorted according to either their natural order or by a specified Comparator.
• Navigable Methods: SortedMap offers methods for navigating through the map in a sorted order, which is useful when you need to access entries in a range.
• Submap Operations: It provides methods like headMap(), tailMap(), and subMap() to view a subset of the map.

---

Core Methods of SortedMap

Here are the key methods defined in the SortedMap interface:

• firstKey(): Returns the first (lowest) key in the map.

  K firstKey();
  

• lastKey(): Returns the last (highest) key in the map.

  K lastKey();
  

• headMap(K toKey): Returns a view of the portion of the map whose keys are less than the specified toKey.

  SortedMap<K, V> headMap(K toKey);
  

• tailMap(K fromKey): Returns a view of the portion of the map whose keys are greater than or equal to the specified fromKey.

  SortedMap<K, V> tailMap(K fromKey);
  

• subMap(K fromKey, K toKey): Returns a view of the portion of the map whose keys range from fromKey to toKey (inclusive of the former and exclusive of the latter).

  SortedMap<K, V> subMap(K fromKey, K toKey);
  

• comparator(): Returns the comparator used to order the keys, or null if the keys are ordered by their natural order.

  Comparator<? super K> comparator();
  

These methods enable you to work with portions of the map, retrieve specific key ranges, and determine the order of the keys. 

---

Example: Using SortedMap with TreeMap

Since SortedMap is an interface, TreeMap is the most commonly used implementation. Here’s an example that demonstrates how to use SortedMap with TreeMap:

import java.util.*;

public class SortedMapExample {
    public static void main(String[] args) {
        // Create a SortedMap using TreeMap (which implements SortedMap)
        SortedMap<String, Integer> sortedMap = new TreeMap<>();

        // Add key-value pairs
        sortedMap.put("Apple", 3);
        sortedMap.put("Banana", 2);
        sortedMap.put("Mango", 1);
        sortedMap.put("Pineapple", 4);

        // Display the entire SortedMap (sorted by keys)
        System.out.println("Sorted Map: " + sortedMap);

        // Retrieve the first and last keys
        System.out.println("First Key: " + sortedMap.firstKey());
        System.out.println("Last Key: " + sortedMap.lastKey());

        // Get a subMap from "Banana" to "Mango"
        SortedMap<String, Integer> subMap = sortedMap.subMap("Banana", "Mango");
        System.out.println("SubMap (Banana to Mango): " + subMap);

        // Get a tailMap starting from "Mango"
        SortedMap<String, Integer> tailMap = sortedMap.tailMap("Mango");
        System.out.println("TailMap (from Mango): " + tailMap);
    }
}

Output:

Sorted Map: {Apple=3, Banana=2, Mango=1, Pineapple=4}
First Key: Apple
Last Key: Pineapple
SubMap (Banana to Mango): {Banana=2}
TailMap (from Mango): {Mango=1, Pineapple=4}

Explanation:

• The TreeMap is used as a SortedMap because it maintains the keys in a sorted order (alphabetically, in this case, because we are using String keys).
• The firstKey() and lastKey() methods return the first and last keys in the map, respectively.
• The subMap() method retrieves a subset of the map that includes the specified key range.
• The tailMap() method returns the portion of the map starting from a specified key.

---

Example: Using Custom Comparator

You can also create a SortedMap with a custom comparator to order the keys in a different way. Here's an example using TreeMap with a custom comparator:

import java.util.*;

public class SortedMapCustomComparatorExample {
    public static void main(String[] args) {
        // Create a SortedMap with custom comparator (reverse order of strings)
        SortedMap<String, Integer> sortedMap = new TreeMap<>(Collections.reverseOrder());

        // Add key-value pairs
        sortedMap.put("Apple", 3);
        sortedMap.put("Banana", 2);
        sortedMap.put("Mango", 1);
        sortedMap.put("Pineapple", 4);

        // Display the entire SortedMap (sorted by keys in reverse order)
        System.out.println("Sorted Map with Custom Comparator: " + sortedMap);
    }
}

Output:

Sorted Map with Custom Comparator: {Pineapple=4, Mango=1, Banana=2, Apple=3}

Explanation:

• We used Collections.reverseOrder() to create a comparator that orders the keys in reverse order.
• The map is displayed with keys sorted in descending order.

---

Difference Between SortedMap and HashMap

Here are key differences between SortedMap and HashMap:

Feature	SortedMap	HashMap
Key Order	Keys are sorted, either naturally or using a comparator.	No guaranteed order of keys.
Performance	Slight overhead for sorting keys.	Faster for random access.
Common Implementations	TreeMap, ConcurrentSkipListMap	HashMap, LinkedHashMap
Navigation Methods	Provides methods like subMap(), headMap(), and tailMap() for working with ranges.	No such methods.

When to Use SortedMap

You should use SortedMap in the following cases:

• When you need a map with keys that are always in sorted order.
• When you need to perform operations that involve ranges of keys, such as extracting a sub-map.
• When you need fast, sorted traversal of the map.

---

---