Sortedmap

SortedMap

Imagine a phone directory that auto-arranges itself 📖 You add entries in any order, but it calmly keeps everything sorted by key.

---

🧠 What is SortedMap?

SortedMap belongs to the Java Collections Framework

```java id="0j2l1n" SortedMap map = new TreeMap<>();

👉 It is a **Map that stores key → value pairs in sorted order of keys**

---

## 🔑 Key Characteristics

* ✔ Keys are **unique**
* ✔ Keys are **automatically sorted**
* ❌ No null keys (in `TreeMap`)
* ✔ Values can be duplicated
* Sorting based on:

    * Natural order (`Comparable`)
    * OR custom `Comparator`

---

## 🏗️ Implementation

### ✔ TreeMap (Primary Implementation)

![Image](https://images.openai.com/static-rsc-4/o-DRRUYfaDqnOGtXzOE-FC5aNCvuiS--n8bMJEogYF1qw_SxcXodpN6oZIlHBET7wQriQUOOQ2ci7cG14VvuWlMf65y50xy0u01CH9Y_8sYSbmosXkUSUYnN1g8yRWFiM0J8Laxs08Oi-OjpJ-GwFpO55qlj4pw7E3u61h_DJ0_no-YfLq9T7lwyEtmRy-k6?purpose=fullsize)

![Image](https://images.openai.com/static-rsc-4/JS2uXoqeJK0lI1NUQLKu_qakwuO9SRsRjSTzk85iXna6w5O6c5w9XmDWjyOuUY2MyRj5co4PnPRscXQEeOtxJg-HNXOXq0sE2fYAVEX7AwDsAJ2IBOnFElN2f68t0RIpIm4tK1-WH8E3mMQJsQWAKyPCg6-Cc2yxAKEMVVAKMr3YstaO4q2M4ZOEht7aRf53?purpose=fullsize)

![Image](https://images.openai.com/static-rsc-4/pdgovD-B8Hycu4eb8TY_3jc508YHUiw1Gj1Wpkgvf9LlFuq4qIuibwl4DjHTAL7J2KmJwmdXxB5u-2GrcuCjXucc9WjGGkYPnVoC_johqzoSEC_0edQZzEhmghWnoKaDn7Ml0CZKYoW21S829pFyy_4gtmWsxl8nFkz-S-Y-BW0jAeSaTsEtYgRWDMBsPbt5?purpose=fullsize)

![Image](https://images.openai.com/static-rsc-4/ywtBaJCrDKoUEu9kgi5H3sfhz3ExOI_Qx68arETiQzNZaOPQUAPDvcF3HvMUTmgFB0enqYVnr2pl5AiSMyip0i5KAdYX6zefT3ahFtPzRAnvAmtArOzkxt0SllCAWdU-hTR_a74AJ4jJNI9mn2mqgutLDqpdNknl49LJYjcijK-EGAXXj8hB1m6DUO17afGq?purpose=fullsize)

![Image](https://images.openai.com/static-rsc-4/Xk-cQUwKaQx2RfuJDnSHMU_7KwgVXrBuY07YVagFlU5fH5C5MehZARNp1llZpDX2Vc1yeZYLBFY9Os5K72a-sK-sQZ2HThNgDpmOo_ZPpniOP9fHGx5OeZLvFGiNYssV1w1CGHvjtl3qToQJ18-OK5NTA8JfDxpOIdRpBzT7_PJMpcWdHGW2Sj43Svm_FVUQ?purpose=fullsize)

```java id="4g0q2x"
SortedMap<String, Integer> map = new TreeMap<>();

• Uses Red-Black Tree 🌳
• Time complexity → O(log n)

---

⚙️ Important Methods

🔹 Basic Map Methods

```java id="yq8x1k" map.put("B", 2); map.put("A", 1); map.put("C", 3);

---

### 🔹 SortedMap Specific Methods

```java id="4k0rjx"
map.firstKey();   // smallest key
map.lastKey();    // largest key

map.headMap("C"); // keys < "C"
map.tailMap("B"); // keys >= "B"
map.subMap("A", "C"); // range [A, C)

---

🧠 Example

```java id="q6v2mw" SortedMap map = new TreeMap<>();

map.put("Banana", 2); map.put("Apple", 1); map.put("Mango", 3);

System.out.println(map);

👉 Output:

```id="l2z9kb"
{Apple=1, Banana=2, Mango=3}

✔ Sorted by keys ✔ No duplicate keys

---

🔄 Custom Sorting Example

```java id="k2q0fz" SortedMap map = new TreeMap<>( (a, b) -> b.compareTo(a) );

map.put("A", 1); map.put("C", 3); map.put("B", 2);

System.out.println(map);

👉 Output:

```id="5y1p9x"
{C=3, B=2, A=1}

---

⚔️ SortedMap vs Map

Feature	SortedMap 🌿	Map
Order	Sorted (by key)	No guarantee
Duplicate keys	Not allowed	Not allowed
Extra methods	Yes	No

---

🎯 Interview Nuggets

• SortedMap is an interface

• Implemented by:

  • TreeMap

  • Extended by:

  • NavigableMap

  • Keys must be Comparable or use Comparator

---

🧠 Memory Trick

SortedMap = Map + Sorted Keys 🌿🗺️