SortedMap and NavigableMap in Java

SortedMap in Java is an interface for maps that keep their keys in sorted order. NavigableMap extends SortedMap and adds methods to find the entry with the closest key, such as "the greatest key less than or equal to 75". These interfaces do for maps what SortedSet and NavigableSet do for sets. TreeMap is the main class that implements them. In this lesson, you will learn their methods with examples.

Declaration

public interface SortedMap<K, V> extends SequencedMap<K, V>
public interface NavigableMap<K, V> extends SortedMap<K, V>

Methods of SortedMap

Methods of NavigableMap

All these methods return null when no key matches.

Example: Grade Boundaries with floorEntry

Let's see an example that turns marks into grades. The keys are the lowest mark for each grade.

import java.util.NavigableMap;
import java.util.TreeMap;
 
public class Grades {
    public static void main(String[] args) {
        NavigableMap<Integer, String> grades = new TreeMap<>();
        grades.put(0, "F");
        grades.put(40, "D");
        grades.put(60, "C");
        grades.put(75, "B");
        grades.put(90, "A");
 
        int[] marks = {91, 75, 74, 38, 60};
        for (int m : marks) {
            System.out.println(m + " -> " + grades.floorEntry(m).getValue());
        }
    }
}

91 -> A
75 -> B
74 -> C
38 -> F
60 -> C

Explanation: floorEntry(m) finds the greatest boundary that is less than or equal to the mark. For 74, that is 60, so the grade is C. For 75, the boundary 75 itself matches, so the grade is B. One method call replaces a long chain of if statements.

Example: Ranges of a Sorted Map

import java.util.NavigableMap;
import java.util.TreeMap;
 
public class Ranges {
    public static void main(String[] args) {
        NavigableMap<Integer, String> timetable = new TreeMap<>();
        timetable.put(9, "Math");
        timetable.put(11, "Physics");
        timetable.put(13, "Lunch");
        timetable.put(14, "Chemistry");
        timetable.put(16, "Sports");
 
        System.out.println("First:     " + timetable.firstEntry());
        System.out.println("Before 13: " + timetable.headMap(13));
        System.out.println("From 13:   " + timetable.tailMap(13));
        System.out.println("11 to 16:  " + timetable.subMap(11, 16));
        System.out.println("Next after 12: " + timetable.ceilingEntry(12));
        System.out.println("Reversed:  " + timetable.descendingMap());
    }
}

First:     9=Math
Before 13: {9=Math, 11=Physics}
From 13:   {13=Lunch, 14=Chemistry, 16=Sports}
11 to 16:  {11=Physics, 13=Lunch, 14=Chemistry}
Next after 12: 13=Lunch
Reversed:  {16=Sports, 14=Chemistry, 13=Lunch, 11=Physics, 9=Math}

Explanation: The keys are hours. headMap(13) gives the morning periods, and tailMap(13) the afternoon ones, including 13. ceilingEntry(12) finds the next period at or after 12 o'clock.

Common Mistakes

Calling .getValue() on a floorEntry result without checking for null. A key below the smallest boundary returns null.

Expecting subMap(a, b) to include b. The end is excluded; use subMap(a, true, b, true) to include it.

Using a HashMap and sorting it every time. Use a TreeMap when sorted keys are needed often.

Practice

1. Easy: Map the hours 6, 12, 17 and 21 to "morning", "afternoon", "evening" and "night", and print the part of the day for any hour with floorEntry.
2. Harder: Store tax slabs (income threshold to tax rate) in a NavigableMap and compute the tax rate for several incomes.

Key Takeaways