Java SortedMap Tutorial

Tags: , ,

In this post, I will use examples to show how to use Java Sorted Map. A SortedMap is a Map that sort its entries in ascending order according to the keys’ natural ordering, or according to a Comparator provided at the time of building a SortedMap. SortedMap is useful if you want to quickly locate an entry that is larger than a specified key. For example, it can be used to implement a Consistent hash

Since the entries in SortedMap are sorted by keys, all the keys in a sortedMap must implement the Comparable interface or provided a comparator when creating the SortedMap. The comparator will be used to sort the keys.  If the keys do not implement Comparable interface, or there is no provided Comparator,  a ClassCastException will be thrown. 

Java Sort Objects using Comparable or Comparator

You may refer to this post for examples on how to sort Java objects using comparable or comparator. 

Java SortedMap

Java SortedMap is an interface, which has the following signature:

Interface SortedMap<K,V>

Type Parameters:
K – the type of keys maintained by this map
V – the type of mapped values
All Superinterfaces:
Map<K,V>
 This means, it is a kind of Java Map, which stores key value pairs. You can also consider it as a sorted HashTable. 
 

All SortedMap implementation classes must provide four “standard” constructors.

The expected “standard” constructors for all sorted map implementations are:

  1. A void (no arguments) constructor, which creates an empty sorted map sorted according to the natural ordering of its keys.
  2. A constructor with a single argument of type Comparator, which creates an empty sorted map sorted according to the specified comparator.
  3. A constructor with a single argument of type Map, which creates a new map with the same key-value mappings as its argument, sorted according to the keys’ natural ordering.
  4. A constructor with a single argument of type SortedMap, which creates a new sorted map with the same key-value mappings and the same ordering as the input sorted map.

See the following examples:

1. Java SortedMap with empty Contructor

SortedMap sortedMap = new TreeMap();

This will create an empty SortedMap sorted according to the natural ordering of its keys.

2. Java SortedMap with Comparator

Comparator comparator = new MyComparator();
SortedMap sortedMap = new TreeMap(comparator);

The constructor with a single argument of type Comparator,  means the value in the SortedMap will be sorted according to the specified Comparator.

3. Java SortedMap with an Map object

Map map = new HashMap();
SortedMap sortedMap = new TreeMap(map);

This constructor accepts a single argument of type Map, which creates a new Map with the same key-value mappings as its argument, sorted according to the keys’ natural ordering.

4. Java SortedMap with an SortedMap object

SortedMap sortedMap= new TreeMap();
SortedMap newSortedMap = new TreeMap(sortedMap);

This constructor accepts a single argument of type SortedMap, which creates a new SortedMap with the same key-value mappings and the same ordering as the input SortedMap.

 

Java SortedMap Methods

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

 
entrySet()

Returns a Set view of the mappings contained in this map.
 
firstKey()

Returns the first (lowest) key currently in this map.
 
headMap(K toKey)

Returns a view of the portion of this map whose keys are strictly less than toKey.
 
keySet()

Returns a Set view of the keys contained in this map.
 
lastKey()

Returns the last (highest) key currently in this map.
 
subMap(K fromKey, K toKey)

Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.
 
tailMap(K fromKey)

Returns a view of the portion of this map whose keys are greater than or equal to fromKey.
 
values()

Returns a Collection view of the values contained in this map.
 
 

Java SortedMap Examples:

Here are some examples to show how to use the Java SortedMap methods. The Student class is defines three attributes: name, age, and score. The code for student class can be found in this the article: java sort examples using comparable or comparator. 
 

The output:

unsorted HashMap..
Key : 35 Value : Student Info: <name = Bei,age=24,score=95.0>
Key : 22 Value : Student Info: <name = Jack,age=22,score=91.0>
Key : 55 Value : Student Info: <name = Jim,age=21,score=87.0>
Key : 41 Value : Student Info: <name = Jin,age=23,score=80.0>
Key : 30 Value : Student Info: <name = Lily,age=20,score=90.0>

Sorted Map in ascending order of student Id…
Key : 22 Value : Student Info: <name = Jack,age=22,score=91.0>
Key : 30 Value : Student Info: <name = Lily,age=20,score=90.0>
Key : 35 Value : Student Info: <name = Bei,age=24,score=95.0>
Key : 41 Value : Student Info: <name = Jin,age=23,score=80.0>
Key : 55 Value : Student Info: <name = Jim,age=21,score=87.0>

Sorted Map in descedning order of student score
Key : 35 Value : Student Info: <name = Bei,age=24,score=95.0>
Key : 22 Value : Student Info: <name = Jack,age=22,score=91.0>
Key : 30 Value : Student Info: <name = Lily,age=20,score=90.0>
Key : 55 Value : Student Info: <name = Jim,age=21,score=87.0>
Key : 41 Value : Student Info: <name = Jin,age=23,score=80.0>

get the students whose id are larger than or equal to 30
Key : 30 Value : Student Info: <name = Lily,age=20,score=90.0>
Key : 35 Value : Student Info: <name = Bei,age=24,score=95.0>
Key : 41 Value : Student Info: <name = Jin,age=23,score=80.0>
Key : 55 Value : Student Info: <name = Jim,age=21,score=87.0>

the first student whose id is larger than 29
id=30Student Info: <name = Lily,age=20,score=90.0>

get the students whose id are smaller than 42
Key : 22 Value : Student Info: <name = Jack,age=22,score=91.0>
Key : 30 Value : Student Info: <name = Lily,age=20,score=90.0>
Key : 35 Value : Student Info: <name = Bei,age=24,score=95.0>
Key : 41 Value : Student Info: <name = Jin,age=23,score=80.0>

http://docs.oracle.com/javase/8/docs/api/java/util/SortedMap.html