Java.Collections.How does SortedMap “sort” itself, other than the fact that toString() outputs all elements in order?

✅ Yes — SortedMap is an interface in Java.

It is part of the Java Collections Framework, and it defines the contract for a map that maintains sorted order of keys.

public interface SortedMap<K, V> extends Map<K, V> {
    Comparator<? super K> comparator();
    SortedMap<K, V> subMap(K fromKey, K toKey);
    SortedMap<K, V> headMap(K toKey);
    SortedMap<K, V> tailMap(K fromKey);
    K firstKey();
    K lastKey();
}

🔹 How does SortedMap “sort” itself?

✅ Short answer:

SortedMap (typically implemented by TreeMap) maintains the sorted order of its keys at all times, not just when printing.

✅ It is always sorted internally — not just visually in toString()!

---

🧠 Under the hood

The most common implementation of SortedMap is:

public class TreeMap<K, V> implements SortedMap<K, V>

➡️ And TreeMap is backed by a Red-Black Tree, which is a type of self-balancing binary search tree (BST).

• Every time you call put(), remove(), get(), or entrySet().iterator(), the tree is traversed in sorted order based on the keys.
• No need to call sort() or do anything special — it’s sorted by design.

---

🔄 How it’s sorted?

It depends on:

1. Natural ordering of the key (Comparable<K>)

TreeMap<Integer, String> map = new TreeMap<>();

→ Sorted by Integer’s natural order

A custom comparator you supply:

TreeMap<String, String> map = new TreeMap<>(Comparator.reverseOrder());

→ Sorted in reverse order

🧪 Proof: It’s not just toString()

You can test it:

SortedMap<Integer, String> map = new TreeMap<>();
map.put(5, "five");
map.put(1, "one");
map.put(3, "three");

System.out.println("First key: " + map.firstKey()); // 1
System.out.println("Last key: " + map.lastKey());   // 5

✅ These methods (firstKey(), lastKey(), subMap(), etc.) rely on true internal ordering, not string formatting.

---

🔥 Real benefit

Since the map is sorted internally, you get powerful methods like:

map.headMap(4);  // keys < 4
map.tailMap(3);  // keys >= 3
map.subMap(2, 5); // keys in [2, 5)

All of these depend on the tree structure and sorted keys, not just the output.

---

🧠 TL;DR:

SortedMap (via TreeMap) actually maintains sorted keys internally using a self-balancing binary search tree.
It’s not just that toString() shows them in order — the entire structure operates in sorted key order all the time.