NavigableMap in Java

A NavigableMap is a subinterface of SortedMap that provides navigation methods to search, traverse, and retrieve entries based on the closest match to a given key.

It belongs to java.util package and is most commonly implemented by TreeMap.

---

Where NavigableMap Fits in the Collection Hierarchy

Map
 └── SortedMap
       └── NavigableMap
             └── TreeMap (Main Implementation)

---

What is NavigableMap?

A NavigableMap is a sorted map that allows:

• Finding closest keys (higher, lower, ceiling, floor)
• Getting first or last entry
• Reverse-order views
• Range views (subMap, headMap, tailMap)
• Bidirectional navigation

Keys are always stored in sorted order (ascending by default).

---

Key Navigation Terms

Method	Meaning
lowerKey(k)	Returns key < k
floorKey(k)	Returns key ≤ k
ceilingKey(k)	Returns key ≥ k
higherKey(k)	Returns key > k

---

Example Structure of NavigableMap

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

map.put(10, "A");
map.put(20, "B");
map.put(30, "C");
map.put(40, "D");

Map (sorted):

10=A  20=B  30=C  40=D

Navigation Examples:

• lowerKey(20) → 10
• floorKey(20) → 20
• ceilingKey(25) → 30
• higherKey(30) → 40

---

Important Methods of NavigableMap

1. Navigational Methods

Method	Description
lowerKey(K key)	Returns the nearest key < key
floorKey(K key)	Returns key ≤ key
ceilingKey(K key)	Returns key ≥ key
higherKey(K key)	Returns key > key
lowerEntry(K key)	Returns Map.Entry < key
floorEntry(K key)	Returns Map.Entry ≤ key
ceilingEntry(K key)	Returns Map.Entry ≥ key
higherEntry(K key)	Returns Map.Entry > key

---

2. First & Last Methods

Method	Description
firstKey()	First (smallest) key
lastKey()	Last (largest) key
firstEntry()	First entry
lastEntry()	Last entry
pollFirstEntry()	Retrieves & removes first entry
pollLastEntry()	Retrieves & removes last entry

---

3. Descending Methods

Method	Description
descendingMap()	Reverse view of the map
descendingKeySet()	Reverse set of keys

---

4. Range / SubMap Methods

Method	Meaning
subMap(fromKey, toKey)	Range view
headMap(toKey)	All keys < toKey
tailMap(fromKey)	All keys ≥ fromKey
Overloaded versions	With boolean for inclusive/exclusive

---

Example Code of NavigableMap

import java.util.*;

public class NavigableMapExample {
    public static void main(String[] args) {
        NavigableMap<Integer, String> map = new TreeMap<>();

        map.put(10, "A");
        map.put(20, "B");
        map.put(30, "C");
        map.put(40, "D");

        System.out.println("Map: " + map);

        System.out.println("lowerKey(20): " + map.lowerKey(20));   // 10
        System.out.println("floorKey(20): " + map.floorKey(20));   // 20
        System.out.println("ceilingKey(25): " + map.ceilingKey(25)); // 30
        System.out.println("higherKey(30): " + map.higherKey(30)); // 40

        System.out.println("Descending Map: " + map.descendingMap());
    }
}

---

Output

Map: {10=A, 20=B, 30=C, 40=D}
lowerKey(20): 10
floorKey(20): 20
ceilingKey(25): 30
higherKey(30): 40
Descending Map: {40=D, 30=C, 20=B, 10=A}

---

When to Use NavigableMap?

Use NavigableMap when you need:

• Sorted key-value data
• Efficient searching for closest key
• Binary-search-based navigation
• Range queries
• Reverse traversal

---

Main Implementation Classes

Class	Description
TreeMap	Most common implementation
ConcurrentSkipListMap	Thread-safe sorted map