SortedMap Interface in Java – Guide with Examples

Q: What is a SortedMap in Java?

SortedMap is an interface in java.util for maps whose entries are kept in ascending key order. It adds firstKey(), lastKey(), range views and comparator() to the Map interface.

Q: Which classes implement SortedMap?

TreeMap and ConcurrentSkipListMap (both through NavigableMap), plus the unmodifiable and synchronized wrappers from Collections.

Q: How does SortedMap order its keys?

By the keys' natural ordering via compareTo(), or by a Comparator passed to the implementation's constructor.

Q: What does comparator() return?

The Comparator used to order the keys, or null if the map uses natural ordering.

Q: Is headMap() inclusive?

No. headMap(k) contains keys strictly less than k. tailMap(k) includes k. Use NavigableMap's headMap(k, true) to include the bound.

Q: What happens if I put an out-of-range key into a sub-map view?

The view throws IllegalArgumentException, because the key does not belong to its range.

Q: What happens when firstKey() is called on an empty SortedMap?

It throws NoSuchElementException. Check isEmpty() first, or use firstEntry(), which returns null for an empty map.

Q: Does SortedMap allow null keys?

Not with natural ordering: TreeMap throws NullPointerException for a null key. null values are allowed in TreeMap.

Q: What is the difference between SortedMap and NavigableMap?

NavigableMap extends SortedMap and adds lowerKey(), floorKey(), ceilingKey(), higherKey(), their entry versions, pollFirstEntry(), pollLastEntry(), descendingMap() and range methods with inclusive flags.

SortedMap is a Map that keeps its entries ordered by key. It adds methods to get the first and last keys and to take range views of the map, such as "all products under ₹1,000".

It is an interface in java.util, part of the Collections Framework since JDK 1.2. Its main implementation is TreeMap. This tutorial explains every SortedMap method with examples.

1. What Is a SortedMap?

A SortedMap guarantees that its keySet(), values() and entrySet() all iterate in ascending key order. The order comes from the keys' natural ordering (Comparable) or from a Comparator supplied when the map is created.

Keys always sorted.
Endpoints: firstKey() and lastKey().
Range views: headMap(), tailMap() and subMap().
comparator() returns the comparator in use, or null for natural order.
Keys are compared with compareTo() or the comparator, not with equals().

2. Hierarchy and Declaration

java.util.SortedMap

public interface SortedMap<K, V> extends SequencedMap<K, V>   // Java 21+
// before Java 21: public interface SortedMap<K, V> extends Map<K, V>

Hierarchy

Map
 └─ SequencedMap (Java 21)
     └─ SortedMap
         └─ NavigableMap
             ├─ TreeMap
             └─ ConcurrentSkipListMap

3. Creating and Using a SortedMap

SortedMapBasics.java

import java.util.SortedMap;
import java.util.TreeMap;

public class SortedMapBasics {
    public static void main(String[] args) {
        SortedMap<Integer, String> rank = new TreeMap<>();
        rank.put(3, "Kiran");
        rank.put(1, "Asha");
        rank.put(2, "Ravi");

        System.out.println("Ranks:        " + rank);
        System.out.println("firstKey():   " + rank.firstKey());
        System.out.println("lastKey():    " + rank.lastKey());
        System.out.println("comparator(): " + rank.comparator());
        System.out.println("keySet():     " + rank.keySet() + "  values(): " + rank.values());
    }
}

Output

Ranks:        {1=Asha, 2=Ravi, 3=Kiran}
firstKey():   1
lastKey():    3
comparator(): null
keySet():     [1, 2, 3]  values(): [Asha, Ravi, Kiran]

The entries were added as 3, 1, 2 but come back as 1, 2, 3. comparator() returns null because the map uses the natural order of Integer.

4. SortedMap Methods

Method	Description
`K firstKey()`	The lowest key; throws `NoSuchElementException` if empty.
`K lastKey()`	The highest key; throws `NoSuchElementException` if empty.
`SortedMap<K,V> headMap(K toKey)`	View of entries with keys strictly less than `toKey`.
`SortedMap<K,V> tailMap(K fromKey)`	View of entries with keys greater than or equal to `fromKey`.
`SortedMap<K,V> subMap(K fromKey, K toKey)`	View from `fromKey` (inclusive) to `toKey` (exclusive).
`Comparator<? super K> comparator()`	The comparator, or `null` for natural ordering.
`keySet()`, `values()`, `entrySet()`	Views that iterate in ascending key order.
`firstEntry()`, `lastEntry()`, `pollFirstEntry()`, `pollLastEntry()`, `reversed()`	Sequenced methods (Java 21).

5. Range Views: headMap, tailMap and subMap

Here a price list is split into ranges. Note that views are live in both directions:

SortedMapRanges.java

import java.util.SortedMap;
import java.util.TreeMap;

public class SortedMapRanges {
    public static void main(String[] args) {
        SortedMap<Integer, String> products = new TreeMap<>();   // price -> product
        products.put(199, "cable");
        products.put(499, "mouse");
        products.put(999, "keyboard");
        products.put(2499, "headphones");
        products.put(15999, "monitor");

        System.out.println("Under 1000:      " + products.headMap(1000));
        System.out.println("1000 and above:  " + products.tailMap(1000));
        System.out.println("400 to 2999:     " + products.subMap(400, 3000));

        SortedMap<Integer, String> cheap = products.headMap(1000);   // live view
        products.put(299, "charger");
        System.out.println("Cheap view now:  " + cheap);

        cheap.remove(199);                                            // removes from products too
        System.out.println("All products:    " + products);
    }
}

Output

Under 1000:      {199=cable, 499=mouse, 999=keyboard}
1000 and above:  {2499=headphones, 15999=monitor}
400 to 2999:     {499=mouse, 999=keyboard, 2499=headphones}
Cheap view now:  {199=cable, 299=charger, 499=mouse, 999=keyboard}
All products:    {299=charger, 499=mouse, 999=keyboard, 2499=headphones, 15999=monitor}

The lower bound is inclusive, the upper bound exclusive.
The charger added to the full map appeared in the cheap view.
Removing 199 through the view removed the cable from the full map.
Putting a key outside a view's range through that view throws IllegalArgumentException.

6. Custom Key Order with a Comparator

Sorting strings as text puts "1.10" before "1.2", which is wrong for version numbers. A comparator that compares the numeric parts fixes it:

VersionOrder.java

import java.util.Comparator;
import java.util.SortedMap;
import java.util.TreeMap;

public class VersionOrder {
    // Compare "1.10" and "1.9" by their numeric parts, not as text
    static final Comparator<String> BY_VERSION = (a, b) -> {
        String[] x = a.split("\\."), y = b.split("\\.");
        for (int i = 0; i < Math.max(x.length, y.length); i++) {
            int p = i < x.length ? Integer.parseInt(x[i]) : 0;
            int q = i < y.length ? Integer.parseInt(y[i]) : 0;
            if (p != q) return Integer.compare(p, q);
        }
        return 0;
    };

    public static void main(String[] args) {
        String[] versions = {"1.10", "1.2", "1.9", "2.0", "1.2.1"};

        SortedMap<String, String> asText = new TreeMap<>();
        SortedMap<String, String> asVersion = new TreeMap<>(BY_VERSION);
        for (String v : versions) {
            asText.put(v, "release");
            asVersion.put(v, "release");
        }
        System.out.println("Text order:    " + asText.keySet());
        System.out.println("Version order: " + asVersion.keySet());
        System.out.println("Latest:        " + asVersion.lastKey());
    }
}

Output

Text order:    [1.10, 1.2, 1.2.1, 1.9, 2.0]
Version order: [1.2, 1.2.1, 1.9, 1.10, 2.0]
Latest:        2.0

The comparator treats "1.2" and "1.2.0" as equal, so in this map they would be the same key. Design comparators carefully, because they decide what a duplicate key is.

7. Java 21: First, Last and Reversed

Since Java 21, SortedMap extends SequencedMap. Methods that read or remove at the ends work; methods that insert at a chosen end do not, because the sort order decides each key's position.

SequencedSortedMap.java

import java.util.SortedMap;
import java.util.TreeMap;

public class SequencedSortedMap {
    public static void main(String[] args) {
        SortedMap<String, Integer> scores = new TreeMap<>();
        scores.put("delta", 4);
        scores.put("alpha", 1);
        scores.put("charlie", 3);

        // Java 21: SortedMap is a SequencedMap
        System.out.println("firstEntry():     " + scores.firstEntry());
        System.out.println("lastEntry():      " + scores.lastEntry());
        System.out.println("reversed():       " + scores.reversed());
        System.out.println("pollFirstEntry(): " + scores.pollFirstEntry() + " -> " + scores);

        try {
            scores.putFirst("zulu", 26);     // position is decided by the sort order
        } catch (UnsupportedOperationException e) {
            System.out.println("putFirst(): UnsupportedOperationException");
        }
    }
}

Output

firstEntry():     alpha=1
lastEntry():      delta=4
reversed():       {delta=4, charlie=3, alpha=1}
pollFirstEntry(): alpha=1 -> {charlie=3, delta=4}
putFirst(): UnsupportedOperationException

8. Implementations

Class	Structure	Thread-safe	Notes
TreeMap	Red-black tree	No	The usual choice; O(log n).
`ConcurrentSkipListMap`	Skip list	Yes	Concurrent sorted map.
`Collections.unmodifiableSortedMap()`	Wrapper	Read-only	Rejects changes.
`Collections.synchronizedSortedMap()`	Wrapper	Yes (locks)	Lock it manually while iterating.

9. SortedMap vs NavigableMap

NavigableMap (Java 6) extends SortedMap with nearest-key lookups and more flexible ranges:

Need	SortedMap	NavigableMap
First/last key	`firstKey()`, `lastKey()`	Same, plus `firstEntry()`, `pollFirstEntry()`…
Nearest key	No	`floorKey()`, `ceilingKey()`, `lowerKey()`, `higherKey()`
Inclusive/exclusive bounds	Fixed	Chosen per bound
Reverse view	`reversed()` (Java 21)	`descendingMap()`

10. Rules for Keys

With natural ordering, keys must implement Comparable, otherwise ClassCastException.
null keys are not allowed with natural ordering.
Keys that compare as 0 are the same key, even if equals() disagrees.
Do not modify a key's sort fields while it is in the map.

11. Summary

SortedMap keeps entries in ascending key order.
It adds firstKey(), lastKey(), headMap(), tailMap(), subMap() and comparator().
Range views are live, inclusive at the start and exclusive at the end.
TreeMap is the main implementation; ConcurrentSkipListMap is the concurrent one.
NavigableMap extends it with nearest-key methods and flexible ranges.

Frequently Asked Questions (FAQ)

Q1. What is a SortedMap in Java?

SortedMap is an interface in java.util for maps whose entries are kept in ascending key order. It adds firstKey(), lastKey(), range views and comparator() to the Map interface.

Q2. Which classes implement SortedMap?

TreeMap and ConcurrentSkipListMap (both through NavigableMap), plus the unmodifiable and synchronized wrappers from Collections.

Q3. How does SortedMap order its keys?

By the keys' natural ordering via compareTo(), or by a Comparator passed to the implementation's constructor.

Q4. What does comparator() return?

The Comparator used to order the keys, or null if the map uses natural ordering.

Q5. Is headMap() inclusive?

No. headMap(k) contains keys strictly less than k. tailMap(k) includes k. Use NavigableMap's headMap(k, true) to include the bound.

Q6. Are headMap(), tailMap() and subMap() copies of the map?

No, they are live views. Changes in the original map appear in the view and vice versa, within the view's key range.

Q7. What happens if I put an out-of-range key into a sub-map view?

The view throws IllegalArgumentException, because the key does not belong to its range.

Q8. What happens when firstKey() is called on an empty SortedMap?

It throws NoSuchElementException. Check isEmpty() first, or use firstEntry(), which returns null for an empty map.

Q9. Does SortedMap allow null keys?

Not with natural ordering: TreeMap throws NullPointerException for a null key. null values are allowed in TreeMap.

Q10. What is the difference between SortedMap and NavigableMap?

NavigableMap extends SortedMap and adds lowerKey(), floorKey(), ceilingKey(), higherKey(), their entry versions, pollFirstEntry(), pollLastEntry(), descendingMap() and range methods with inclusive flags.

Q11. What is the difference between SortedMap and a HashMap?

A HashMap has no order and O(1) operations. A SortedMap such as TreeMap keeps keys sorted, supports ranges and endpoints, and has O(log n) operations.

Q12. How do I iterate a SortedMap in reverse order?

On Java 21, use map.reversed(). With a NavigableMap on any version, use descendingMap().

Q13. Can a SortedMap be sorted by values?

No, the order is always by key. Sort the entries by value with a stream and collect them into a LinkedHashMap if you need value order.

Q14. Is SortedMap thread-safe?

The interface does not decide that. TreeMap is not thread-safe; ConcurrentSkipListMap is. Collections.synchronizedSortedMap() creates a synchronized wrapper.

Q15. Why does putFirst() throw an exception on a SortedMap?

A sorted map decides each key's position from the comparison order, so it cannot honour a request to put a key at a specific end. The Java 21 putFirst() and putLast() methods therefore throw UnsupportedOperationException.

Q16. How are duplicate keys detected in a SortedMap?

By comparison: if the comparator or compareTo() returns 0, the keys are the same, and put() replaces the existing value.

Q17. What is the time complexity of SortedMap operations in a TreeMap?

get, put, remove, firstKey and lastKey are O(log n). Creating a range view is fast; iterating it costs time proportional to its size.

Q18. How do I make a read-only SortedMap?

Wrap it: Collections.unmodifiableSortedMap(map). The view rejects changes but reflects later changes to the underlying map.

Q19. What is the relation between SortedMap and SortedSet?

They mirror each other. firstKey() matches first(), headMap() matches headSet() and so on. A SortedMap's keySet() behaves like a sorted set of its keys.

Q20. When should I declare a variable as SortedMap?

When your code needs only sorted iteration, endpoints and simple ranges. If it needs nearest-key lookups or inclusive ranges, declare it as NavigableMap instead.

Was this tutorial helpful?

Help Us Improve

SortedMap Interface in Java – Guide with Examples

1. What Is a SortedMap?

2. Hierarchy and Declaration

3. Creating and Using a SortedMap

4. SortedMap Methods

5. Range Views: headMap, tailMap and subMap

6. Custom Key Order with a Comparator

7. Java 21: First, Last and Reversed

8. Implementations

9. SortedMap vs NavigableMap

10. Rules for Keys

11. Summary

Related Tutorials

Frequently Asked Questions (FAQ)