Learnitweb

Java NavigableMap Tutorial

The NavigableMap interface is part of the Java Collections Framework and belongs to the java.util package. It extends the SortedMap interface and provides navigation methods to find entries or keys based on their order.

The most common implementation of NavigableMap is TreeMap, which stores key-value pairs in sorted order based on natural ordering of keys or a custom comparator.

1. Overview of NavigableMap

  • Definition: NavigableMap<K, V> is a sorted map that allows navigation methods to find entries or keys relative to a specified key.
  • Hierarchy:
java.util.Map<K, V>
    -> java.util.SortedMap<K, V>
        -> java.util.NavigableMap<K, V>
  • Common Implementations:
    • TreeMap – fully implements NavigableMap.
    • ConcurrentSkipListMap – a thread-safe implementation suitable for concurrent environments.
  • Key Characteristics:
    1. Sorted Keys: Keys are maintained in ascending order.
    2. Navigation Support: Methods for nearest matches (lowerKey, floorKey, ceilingKey, higherKey).
    3. Subset Views: Return submaps with a specific key range.
    4. Optional Descending Order View: Access keys in reverse order.

2. Key Features of NavigableMap

  1. Sorted Key Set: Maintains keys in a sorted order according to natural ordering or a comparator.
  2. Navigation Methods: Find entries or keys closest to a given key.
  3. Submap Views: Return ranges (subMap, headMap, tailMap) as live views of the map.
  4. Descending Map: Reverse-order view of keys.
  5. Efficient Operations: Most operations are O(log n) in TreeMap.
  6. Thread-Safe Variants: Use ConcurrentSkipListMap for concurrency without external synchronization.

3. Commonly Used Methods

3.1 Basic Map Operations

  • put(K key, V value) – Adds or updates a key-value pair.
  • get(Object key) – Retrieves the value for a key.
  • remove(Object key) – Removes the mapping for a key.
  • containsKey(Object key) – Checks if a key exists.
  • containsValue(Object value) – Checks if a value exists.
NavigableMap<Integer, String> map = new TreeMap<>();
map.put(10, "Java");
map.put(20, "Python");
map.put(30, "C++");

System.out.println(map.get(20)); // Python
System.out.println(map.containsKey(10)); // true
map.remove(30);
System.out.println(map); // {10=Java, 20=Python}

3.2 Navigation Methods

These methods allow finding keys or entries relative to a specified key:

MethodDescription
lowerKey(K key)Greatest key less than the given key, or null.
floorKey(K key)Greatest key less than or equal to the given key.
ceilingKey(K key)Smallest key greater than or equal to the given key.
higherKey(K key)Smallest key greater than the given key.
lowerEntry(K key)Returns entry (key-value pair) for lowerKey.
floorEntry(K key)Returns entry for floorKey.
ceilingEntry(K key)Returns entry for ceilingKey.
higherEntry(K key)Returns entry for higherKey.
NavigableMap<Integer, String> map = new TreeMap<>();
map.put(10, "A");
map.put(20, "B");
map.put(30, "C");

System.out.println(map.lowerKey(25));  // 20
System.out.println(map.floorKey(20));  // 20
System.out.println(map.ceilingKey(15)); // 20
System.out.println(map.higherKey(20)); // 30
System.out.println(map.ceilingEntry(15)); // 20=B

3.3 Polling Methods

  • pollFirstEntry() – Removes and returns the first entry (lowest key).
  • pollLastEntry() – Removes and returns the last entry (highest key).
NavigableMap<Integer, String> map = new TreeMap<>();
map.put(10, "A");
map.put(20, "B");
map.put(30, "C");

System.out.println(map.pollFirstEntry()); // 10=A
System.out.println(map.pollLastEntry());  // 30=C
System.out.println(map); // {20=B}

3.4 Submap Views

  • subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) – Returns a live view of the map between fromKey and toKey.
  • headMap(K toKey, boolean inclusive) – Returns a live view of keys less than or equal to toKey.
  • tailMap(K fromKey, boolean inclusive) – Returns a live view of keys greater than or equal to fromKey.
NavigableMap<Integer, String> map = new TreeMap<>();
map.put(10, "A");
map.put(20, "B");
map.put(30, "C");
map.put(40, "D");

NavigableMap<Integer, String> subMap = map.subMap(15, true, 35, false);
System.out.println(subMap); // {20=B, 30=C}

NavigableMap<Integer, String> headMap = map.headMap(30, true);
System.out.println(headMap); // {10=A, 20=B, 30=C}

NavigableMap<Integer, String> tailMap = map.tailMap(20, false);
System.out.println(tailMap); // {30=C, 40=D}

Live view: Changes in the submap affect the original map and vice versa.

3.5 Descending Map

  • descendingMap() – Returns a view of the map with keys in reverse order.
NavigableMap<Integer, String> map = new TreeMap<>();
map.put(10, "A");
map.put(20, "B");
map.put(30, "C");

NavigableMap<Integer, String> descMap = map.descendingMap();
System.out.println(descMap); // {30=C, 20=B, 10=A}

3.6 Navigable KeySet

  • navigableKeySet() – Returns a NavigableSet of keys in ascending order.
  • descendingKeySet() – Returns a NavigableSet of keys in descending order.
NavigableSet<Integer> keys = map.navigableKeySet();
System.out.println(keys); // [10, 20, 30]

NavigableSet<Integer> descKeys = map.descendingKeySet();
System.out.println(descKeys); // [30, 20, 10]

4. Use Cases of NavigableMap

  1. Range Queries:
    Retrieve key-value pairs within a specific range using subMap, headMap, or tailMap.
  2. Closest Match Lookups:
    Find nearest key matches using lowerKey, floorKey, ceilingKey, and higherKey.
    Example: Stock trading platforms, where you need closest buy/sell orders.
  3. Priority Navigation:
    Use pollFirstEntry and pollLastEntry for efficient removal of smallest/largest entries.
    Example: Scheduling systems, leaderboards.
  4. Descending Order Views:
    Reverse order iteration for reports or analytics.
  5. Sorted and Unique Keys:
    Maintains unique keys in sorted order for fast retrieval.

5. Performance Notes

  • TreeMap Implementation:
    • Internally uses a Red-Black Tree.
    • Operations like put, get, remove, and navigation run in O(log n) time.
  • ConcurrentSkipListMap:
    • Thread-safe variant that allows concurrent read/write operations.
    • Also maintains sorted keys with logarithmic complexity.

6. Summary

NavigableMap is a powerful interface for working with sorted key-value pairs:

  • Extends SortedMap with navigation and closest-match methods.
  • Provides submap views for key ranges (subMap, headMap, tailMap).
  • Supports polling and reverse-order operations (pollFirstEntry, pollLastEntry, descendingMap).
  • Efficient with O(log n) operations when using TreeMap.
  • Useful in scenarios requiring sorted, unique keys with navigation or range queries.