NavigableMap interface

In this article, we will discuss NavigableMap interface with all its important methods for navigation support for its implementation class TreeMap in detail

SortedMap doesn’t allow duplicate keys and stores key-value pairs based on some sorting order either natural ordering or customized ordering and provides useful methods for navigation purposes

 

NavigableMap interface:

  • NavigableMap interface is a sub-interface of SortedMap interface (i.e.; NavigableMap extends SortedMap)
  • To represent a group of key-value pairs as a single unit/entity, where duplicates keys aren’t allowed and keys are stored according to some sorting order
  • It allows only unique keys to be inserted
  • Stores key-value pairs in sorting order on the basis of keys only, not values
  • NavigableMap interface defines more specific methods for navigation purposes, in addition to inherited methods from Map/SortedMap interfaces
  • This is introduced in Java 1.6 version for navigation support to TreeMap
  • Present in java.util package and extends java.util.SortedMap interface

33-NavigableMap-interace-in-java

Source: Team BenchResources.Net

 

NavigableMap interface methods:

 NavigableMap methods Description
K floorKey(K key); returns greatest/highest element which is less than or equal to specified key
null if there is no such key
K lowerKey(K key); returns greatest/highest element which is less than specified key

null if there is no such key

K ceilingKey(K key); returns least/lowest element which is greater than or equal to specified key
null if there is no such key
K higherKey(K key) ; returns least/lowest element which is greater than specified key

null if there is no such key

Map.Entry<K,V> pollFirstEntry(); remove & retrieve 1st entry (i.e.; 1st key-value pair)
 
null if invoking map is empty
Map.Entry<K,V> pollLastEntry(); remove & retrieve last entry (i.e.; last key-value pair)
 
null if invoking map is empty
NavigableMap<K,V> descendingMap(); returns invoking map in reverse order

 

Example to understand NavigableMap specific methods

NavigableMap = [10-Alpha, 20-Beta, 30-Gamma, 40-delta, 50-epsilon, 60-lambda, 70-mu];

floorKey(30) = 30-Gamma
lowerKey(30) = 20-Beta
ceilingKey(40) = 40-delta
higherKey(40) = 50-epsilon
pollFirstEntry() = 10-Alpha
pollLastEntry() = 70-mu
descendingMap() = [70-mu, 60-lambda, 50-epsilon, 40-delta, 30-Gamma, 20-Beta, 10-Alpha];

 

NavigableMap example

NavigableMapMethods.java

package in.bench.resources.java.collection;

import java.util.NavigableMap;
import java.util.TreeMap;

public class NavigableMapMethods {

	public static void main(String[] args) {

		// creating NavigableMap reference and TreeMap object
		NavigableMap<Integer, String> nm = new TreeMap<Integer, String>();

		// adding key-value pairs to SortedMap/TreeMap object
		nm.put(3, "Yahoo");
		nm.put(4, "Amazon");
		nm.put(7, "Twiter");
		nm.put(1, "Google");
		nm.put(5, "Reddit");
		nm.put(6, "LinkedIn");
		nm.put(2, "Facebook");

		// printing according to natural ordering
		System.out.println("Elements will be Sorted"
				+ " acc to Natural ordering:\n");
		System.out.println(nm);

		// floorKey and lowerKey methods
		System.out.println("\nfloorKey(3)  : " + nm.floorKey(3));
		System.out.println("\nlowerKey(3)  : " + nm.lowerKey(3));

		// ceilingKey and higherKey methods
		System.out.println("\nceilingKey(4)  : " + nm.ceilingKey(4));
		System.out.println("\nhigherKey(5)  : " + nm.higherKey(5));

		// pollFirstEntry method
		System.out.println("\npollFirstEntry() : " + nm.pollFirstEntry());
		System.out.println("NavigableMap after polling First Entry : "
				+ nm);

		// pollLastEntry method
		System.out.println("\npollLastEntry() : " + nm.pollLastEntry());
		System.out.println("NavigableMap after polling Last Entry : "
				+ nm);

		// descendingMap in descending or reverse order
		System.out.println("\nNavigableMap in descending order : "
				+ nm.descendingMap());
	}
}

Output:

Elements will be Sorted acc to Natural ordering:

{1=Google, 2=Facebook, 3=Yahoo, 4=Amazon, 5=Reddit, 6=LinkedIn, 7=Twiter}

floorKey(3)  : 3

lowerKey(3)  : 2

ceilingKey(4)  : 4

higherKey(5)  : 6

pollFirstEntry() : 1=Google
NavigableMap after polling First Entry : {2=Facebook, 3=Yahoo, 4=Amazon, 
5=Reddit, 6=LinkedIn, 7=Twiter}

pollLastEntry() : 7=Twiter
NavigableMap after polling Last Entry : {2=Facebook, 3=Yahoo, 4=Amazon, 
5=Reddit, 6=LinkedIn}

NavigableMap in descending order : {6=LinkedIn, 5=Reddit, 4=Amazon, 
3=Yahoo, 2=Facebook}

 

 

Note: All methods of NavigableMap is non-synchronized but it can be easily converted into synchronized NavigableMap using utility method of java.util.Collections class

Map map= Collections.synchronizedMap(nm);

 

Class that implements NavigableMap interface

  • TreeMap implements NavigableMap interface

 

Factors to consider while discussing any collection class

We should consider below factors while discussing any implementation class of collection framework or for that matter Map interface,

  • Underlying data structure
  • Duplicates are allowed or Not
  • Insertion order is maintained or Not
  • Whether NULL insertion is possible or Not
  • If possible, how many NULL values can be inserted
  • Whether collection class provide sorting, by default
  • Is there any way to apply customized sorting
  • Performance, while dealing with retrieval or manipulation (addition/deletion)
  • By default, all methods are synchronized or Not

 

References:

https://docs.oracle.com/javase/tutorial/collections/intro/
https://docs.oracle.com/javase/tutorial/collections/interfaces/collection.html
https://docs.oracle.com/javase/7/docs/api/java/util/Collection.html
https://docs.oracle.com/javase/7/docs/api/java/util/Map.html
https://docs.oracle.com/javase/7/docs/api/java/util/Map.Entry.html
https://docs.oracle.com/javase/tutorial/collections/interfaces/map.html
https://docs.oracle.com/javase/7/docs/api/java/util/SortedMap.html
https://docs.oracle.com/javase/tutorial/collections/interfaces/sorted-map.html
https://docs.oracle.com/javase/7/docs/api/java/util/NavigableMap.html

 

Happy Coding !!
Happy Learning !!

TreeMap class
SortedMap interface