Java SortedMap and TreeMap Tutorial and Examples

This tutorial helps you understand SortedMap with TreeMapimplementation in the Java Collections Framework.

First, let’s review the API hierarchy. TreeMap doesn’t only implement the Map interface, it also implements the SortedMap and NavigableMap interfaces. Therefore, besides the behaviors inherited from the Map, TreeMap also inherits the behaviors defined by SortedMap and NavigableMap. The following picture depicts the API hierarchy of TreeMap:

1. Understanding SortedMap

The main characteristic of a SortedMap is that, it orders the keys by their natural ordering, or by a specified comparator. So consider using a TreeMap when you want a map that satisfies the following criteria:

• null key or null value are not permitted.
• The keys are sorted either by natural ordering or by a specified comparator.

The following example realizes the concept of a SortedMap:

SortedMap<String, String> mapDomains = new TreeMap<>();

mapDomains.put(".com", "International");
mapDomains.put(".us", "United States");
mapDomains.put(".uk", "United Kingdom");
mapDomains.put(".jp", "Japan");
mapDomains.put(".au", "Australia");

System.out.println(mapDomains);

Output:

{.au=Australia, .com=International, .jp=Japan, .uk=United Kingdom, .us=United States}

Here, this map contains mappings of domain=country, and as we see in the output, the domains (keys) are sorted by alphabetic order (natural ordering of Strings).

Besides the operations inherited from the Map interface, the SortedMap also defines the following operations:

• Range view: returns a sub sorted map whose keys fall within a range of keys in the original map.
• Endpoints: returns the first or last key in the sorted map.
• Comparator access: returns the comparator (implements the Comparator interface), if any, used to sort the map.

Hence the following code is the definition of a SortedMap:

public interface SortedMap<K, V> extends Map<K, V>{
	Comparator<? super K> comparator();
	SortedMap<K, V> subMap(K fromKey, K toKey);
	SortedMap<K, V> headMap(K toKey);
	SortedMap<K, V> tailMap(K fromKey);
	K firstKey();
	K lastKey();
}

Let’s look at each type of operation in details.

* Range View Operations:

+ subMap(K fromKey, K toKey): returns a sorted map whose keys range from fromKey, inclusive, to toKey, exclusive.

+ headMap(K toKey): returns a sorted map whose keys are strictly less than toKey.

+ tailMap(K fromKey): returns a sorted map whose keys are greater than or equal to fromKey.

* Endpoint operations:

+ firstKey(): returns the first (lowest) key currently in the map.

+ lastKey(): returns the last (highest) key currently in the map.

* Comparator access:

+ comparator(): returns the comparator used to order the keys in the map, or returns null if this map uses the natural ordering of its keys.

2. SortedMap and TreeMap Examples

The following code example demonstrates how to work with these operations on a TreeMap:

SortedMap<Integer, String> mapHttpStatus = new TreeMap<>();

mapHttpStatus.put(100, "Continue");
mapHttpStatus.put(200, "OK");
mapHttpStatus.put(300, "Multiple Choices");

mapHttpStatus.put(400, "Bad Request");
mapHttpStatus.put(401, "Unauthorized");
mapHttpStatus.put(402, "Payment Required");
mapHttpStatus.put(403, "Forbidden");
mapHttpStatus.put(404, "Not Found");

mapHttpStatus.put(500, "Internal Server Error");
mapHttpStatus.put(501, "Not Implemented");
mapHttpStatus.put(502, "Bad Gateway");

System.out.println("All key-value pairs: ");

for (Integer code : mapHttpStatus.keySet()) {
	System.out.println(code + " -> " + mapHttpStatus.get(code));
}

System.out.println();

Integer firstKey = mapHttpStatus.firstKey();
String firstValue = mapHttpStatus.get(firstKey);

System.out.println("First status: " + firstKey + " -> " + firstValue);
System.out.println();

Integer lastKey = mapHttpStatus.lastKey();
String lastValue = mapHttpStatus.get(lastKey);

System.out.println("Last status: " + lastKey + " -> " + lastValue);
System.out.println();


SortedMap<Integer, String> map4xxStatus = mapHttpStatus.subMap(400, 500);

System.out.println("4xx Statuses: ");

for (Integer code : map4xxStatus.keySet()) {
	System.out.println(code + " -> " + map4xxStatus.get(code));
}

System.out.println();

SortedMap<Integer, String> mapUnder300Status = mapHttpStatus.headMap(300);

System.out.println("Statuses < 300: ");

for (Integer code : mapUnder300Status.keySet()) {
	System.out.println(code + " -> " + mapUnder300Status.get(code));
}

System.out.println();

SortedMap<Integer, String> mapAbove500Status = mapHttpStatus.tailMap(500);

System.out.println("Statuses > 500: ");

for (Integer code : mapAbove500Status.keySet()) {
	System.out.println(code + " -> " + mapAbove500Status.get(code));
}

Comparator comparator = mapHttpStatus.comparator();

System.out.println("Sorted by natural ordering? " + (comparator == null));

Output:

All key-value pairs:
100 -> Continue
200 -> OK
300 -> Multiple Choices
400 -> Bad Request
401 -> Unauthorized
402 -> Payment Required
403 -> Forbidden
404 -> Not Found
500 -> Internal Server Error
501 -> Not Implemented
502 -> Bad Gateway

First status: 100 -> Continue

Last status: 502 -> Bad Gateway

4xx Statuses:
400 -> Bad Request
401 -> Unauthorized
402 -> Payment Required
403 -> Forbidden
404 -> Not Found

Statuses < 300:
100 -> Continue
200 -> OK

Statuses > 500:
500 -> Internal Server Error
501 -> Not Implemented
502 -> Bad Gateway
Sorted by natural ordering? true

And the following example shows how to use a comparator:

SortedMap<Integer, String> mapHttpStatus = new TreeMap<>(new ReverseComparator());

mapHttpStatus.put(100, "Continue");
mapHttpStatus.put(200, "OK");
mapHttpStatus.put(300, "Multiple Choices");

mapHttpStatus.put(400, "Bad Request");
mapHttpStatus.put(401, "Unauthorized");
mapHttpStatus.put(402, "Payment Required");
mapHttpStatus.put(403, "Forbidden");
mapHttpStatus.put(404, "Not Found");

mapHttpStatus.put(500, "Internal Server Error");
mapHttpStatus.put(501, "Not Implemented");
mapHttpStatus.put(502, "Bad Gateway");

for (Integer code : mapHttpStatus.keySet()) {
	System.out.println(code + " -> " + mapHttpStatus.get(code));
}

Here’s the code of the comparator class:

class ReverseComparator implements Comparator<Integer> {
	public int compare(Integer num1, Integer num2) {
		return num2.compareTo(num1);
	}
}

Output:

502 -> Bad Gateway
501 -> Not Implemented
500 -> Internal Server Error
404 -> Not Found
403 -> Forbidden
402 -> Payment Required
401 -> Unauthorized
400 -> Bad Request
300 -> Multiple Choices
200 -> OK
100 -> Continue

As you can see, this comparator sorts the map by the descending order of its keys.

In case you are working on Java 8, use Lambda expressions to shorten the comparator code like this:

SortedMap<Integer, String> mapHttpStatus = new TreeMap<>((i1, i2) -> i2.compareTo(i1));

References:

• The SortedMap Interface (The Java Tutorials)
• SortedMap Interface Javadoc
• TreeMap Class Javadoc

Related Java Map tutorials:

• Java Map Tutorial
•  Java NavigableMap and TreeMap Tutorial
• Class diagram of Map API

Other Java Collections Tutorials:

• Java Set Collection Tutorial and Examples
• Java Map Collection Tutorial and Examples
• Java Queue Collection Tutorial and Examples
• 18 Java Collections and Generics Best Practices
• Understanding equals and hashCode in Java
• Understanding Object Ordering in Java

About the Author:

Nam Ha Minh is certified Java programmer (SCJP and SCWCD). He began programming with Java back in the days of Java 1.4 and has been passionate about it ever since. You can connect with him on Facebook and watch his Java videos on YouTube.

Attachments:

SortedMapTreeMapExample.java

[SortedMap and TreeMap Code Examples]

3 kB