o7planning

Java SortedMap Tutorial with Examples

  1. SortedMap
  2. Examples
  3. SortedMap Methods
  4. comparator()
  5. firstKey()
  6. lastKey()
  7. subMap(K fromKey, K toKey)
  8. headMap(K toKey)
  9. tailMap(K fromKey)

1. SortedMap

SortedMap is a subinterface of Map, so it has all the characteristics of Map. The difference is that the keys of the SortedMap are sorted in ascending order in their natural order or according to a provided Comparator. Comparator is usually provided at the creation time of the SortedMap object.
public interface SortedMap<K,V> extends Map<K,V>
Here is a comparison between Map and SortedMap:
Map<K,V>
SortedMap<K,V>
NavigableMap<K,V>
Duplicate keys are not allowed.
Can allow null key and null values.
The order of the keys is not guaranteed.
The keys are sorted in ascending order based on their natural order or according to a supplied Comparator.
All SortedMap keys must be Comparable type or you must provide a Comparator for SortedMap to compare keys. Otherwise, ClassCastException will be thrown.
Comparator<K>
If a Comparator is provided for SortedMap, two keys are compared using comparator.compare(key1,key2) method. Consistency with equals must be complied. This means that if comparator.compare(key1,key2)=0 then key1.equals(key2)=true (True for all keys in SortedMap).
  • Java Comparator
Comparable<K>
If Comparator is not provided for SortedMap. All SortedMap keys must be Comparable type for them to be comparable. Keys will be compared with each other according to the key1.equals(key2) rule. Equal consistance should be complied. This means that key1.equals(key2) and key2.equals(key1) must return the same value.

2. Examples

String class implements Comparable interface. Therefore, String objects are comparable, and can be used as keys for SortedMap.
SortedMapEx1.java
package org.o7planning.sortedmap.ex;

import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;

public class SortedMapEx1 {

    public static void main(String[] args) {
        // Create a SortedMap object.
        SortedMap<String, Integer> map = new TreeMap<String, Integer>();
 
        map.put("B", 100);
        map.put("A", 200);
        map.put("F", 400);
        map.put("D", 500);
        map.put("E", 100);

        System.out.println("--- keySet ---");
        Set<String> keys = map.keySet();

        for (String key : keys) {
            System.out.println(key + " --> " + map.get(key));
        }
        
        System.out.println("--- entrySet ---");
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        
        for (Map.Entry<String,Integer> entry: entrySet) {
            System.out.println(entry.getKey() + " --> " + entry.getValue());
        }
    }
}
Output:
--- keySet ---
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400
--- entrySet ---
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400
Note: Basically, TreeMap does not allow null key, unless you provide it with a Comparator that supports comparing null with other values. You can find an example of TreeMap with null key in the following article:
For example: the following OrderLineId class implements Comparable interface, so OrderLineId objects are comparable:
OrderLineId.java
package org.o7planning.beans;

public class OrderLineId implements Comparable<OrderLineId> {
    private int orderId;
    private int line;

    public OrderLineId(int orderId, int line) {
        this.orderId = orderId;
        this.line = line;
    }

    public int getOrderId() {
        return orderId;
    }

    public int getLine() {
        return line;
    }

    @Override
    public int compareTo(OrderLineId other) {
        if (other == null) {
            return 1; // this > other
        }
        if (this.orderId != other.orderId) {
            return this.orderId - other.orderId;
        }
        return this.line - other.line;
    }
}
SortedMapEx2.java
package org.o7planning.sortedmap.ex;

import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;

import org.o7planning.beans.OrderLineId;

public class SortedMapEx2 {

    public static void main(String[] args) {
        // OrderLineId --> String productName.
        SortedMap<OrderLineId, String> sortedMap = new TreeMap<>();
        
        OrderLineId k21 = new OrderLineId(2, 1);
        OrderLineId k12 = new OrderLineId(1, 2);
        OrderLineId k11 = new OrderLineId(1, 1);
        OrderLineId k22 = new OrderLineId(2, 2);
        OrderLineId k31 = new OrderLineId(3, 1);
        OrderLineId k23 = new OrderLineId(2, 3);
        
        sortedMap.put(k21, "Samsung a71");
        sortedMap.put(k12, "IPhone 12");
        sortedMap.put(k11, "Samsung a51");
        sortedMap.put(k22, "IPhone 11");
        sortedMap.put(k31, "IPhone 7");
        sortedMap.put(k23, "Samsung a51");
        
        Set<OrderLineId> keys = sortedMap.keySet();
        
        for(OrderLineId key: keys)  {
            String productName = sortedMap.get(key);
            System.out.println("OrderId: " + key.getOrderId() //
                       + " / Line: " + key.getLine() + " --> " + productName);
        }
    }
}
Output:
OrderId: 1 / Line: 1 --> Samsung a51
OrderId: 1 / Line: 2 --> IPhone 12
OrderId: 2 / Line: 1 --> Samsung a71
OrderId: 2 / Line: 2 --> IPhone 11
OrderId: 2 / Line: 3 --> Samsung a51
OrderId: 3 / Line: 1 --> IPhone 7
For example, the following OrderLineKey class does not implement Comparable interface, so OrderLineKey objects are not comparable. In this case you need to provide a Comparator for SortedMap.
OrderLineKey.java
package org.o7planning.beans;

public class OrderLineKey {
    private int orderId;
    private int line;

    public OrderLineKey(int orderId, int line) {
        this.orderId = orderId;
        this.line = line;
    }

    public int getOrderId() {
        return orderId;
    }

    public int getLine() {
        return line;
    }
}
SortedMapEx3.java
package org.o7planning.sortedmap.ex;

import java.util.Comparator;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;

import org.o7planning.beans.OrderLineKey;

public class SortedMapEx3 {

    public static void main(String[] args) {
        // Comparator.
        OrderLineKeyComparator comparator = new OrderLineKeyComparator();
        
        // Creaate SortedMap with a Comparator.
        // OrderLineKey --> String productName.
        SortedMap<OrderLineKey, String> sortedMap = new TreeMap<>(comparator);

        OrderLineKey k21 = new OrderLineKey(2, 1);
        OrderLineKey k12 = new OrderLineKey(1, 2);
        OrderLineKey k11 = new OrderLineKey(1, 1);
        OrderLineKey k22 = new OrderLineKey(2, 2);
        OrderLineKey k31 = new OrderLineKey(3, 1);
        OrderLineKey k23 = new OrderLineKey(2, 3);

        sortedMap.put(k21, "Samsung a71");
        sortedMap.put(k12, "IPhone 12");
        sortedMap.put(k11, "Samsung a51");
        
        sortedMap.put(null, "<Nothing>");
        
        sortedMap.put(k22, "IPhone 11");
        sortedMap.put(k31, "IPhone 7");
        sortedMap.put(k23, "Samsung a51");

        Set<OrderLineKey> keys = sortedMap.keySet();

        for (OrderLineKey key : keys) {
            String productName = sortedMap.get(key);
            if(key == null)  {
                System.out.println("Null Key --> " + productName);
            } else {
                System.out.println("OrderId: " + key.getOrderId() //
                        + " / Line: " + key.getLine() + " --> " + productName);
            }
        }
    }
}

// This comparator supports null comparison.
class OrderLineKeyComparator implements Comparator<OrderLineKey> {

    @Override
    public int compare(OrderLineKey o1, OrderLineKey o2) {
        if (o1 == o2) {
            return 0;
        }
        if (o1 == null) {
            return -1; // o1 < o2.
        }
        if (o2 == null) {
            return 1; // o1 > o2
        }
        int d = o1.getOrderId() - o2.getOrderId();
        if (d != 0) {
            return d;
        }
        return o1.getLine() - o2.getLine();
    }
}
Output:
Null Key --> <Nothing>
OrderId: 1 / Line: 1 --> Samsung a51
OrderId: 1 / Line: 2 --> IPhone 12
OrderId: 2 / Line: 1 --> Samsung a71
OrderId: 2 / Line: 2 --> IPhone 11
OrderId: 2 / Line: 3 --> Samsung a51
OrderId: 3 / Line: 1 --> IPhone 7

3. SortedMap Methods

SortedMap Methods
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();

// Inherited from Map
Set<K> keySet();
Set<Map.Entry<K, V>> entrySet();      
Collection<V> values();
...

4. comparator()

Comparator<? super K> comparator()
Returns the Comparator used to order the keys in this SortedSet, or null if this SortedSet uses the natural ordering of its keys.

5. firstKey()

K firstKey()
Returns the first (smallest) key currently in this SortedMap.

6. lastKey()

K lastKey()
Returns the last (highest) key currently in this SortedMap.

7. subMap(K fromKey, K toKey)

SortedMap<K,V> subMap(K fromKey, K toKey)
Returns a view of a portion of this SortedMap that includes mappings with keys ranging from fromKey to toKey (fromKey =< key < toKey). (If fromKey and toKey are equal, the returned SortedMap is empty).
The returned SortedMap is related to the current SortedMap. Changes on one SortedMap affect the other SortedMap and vice versa.
SortedMap_subMap_ex1.java
package org.o7planning.sortedmap.ex;

import java.util.SortedMap;
import java.util.TreeMap;

public class SortedMap_subMap_ex1 {

    public static void main(String[] args) {
        SortedMap<String, String> myMap = new TreeMap<>();

        myMap.put("A", "VA");
        myMap.put("B", "VB");
        myMap.put("C", "VC");
        myMap.put("D", "VD");
        myMap.put("E", "VE");

        // A Sub Map
        SortedMap<String, String> subMap = myMap.subMap("B", "C1");

        System.out.println(" -- subMap --");
        for (String s : subMap.keySet()) {
            System.out.println(s + " --> " + subMap.get(s));
        }

        subMap.put("B1", "VB1");
        subMap.put("B2", "VB2");

        System.out.println(" -- subMap (after putting some mappings to subMap) --");
        for (String s : subMap.keySet()) {
            System.out.println(s + " --> " + subMap.get(s));
        }

        System.out.println(" -- myMap (after putting some mappings to subMap) --");
        for (String s : myMap.keySet()) {
            System.out.println(s + " --> " + myMap.get(s));
        }
    }
}
Output:
-- subMap --
B --> VB
C --> VC
 -- subMap (after putting some mappings to subMap) --
B --> VB
B1 --> VB1
B2 --> VB2
C --> VC
 -- myMap (after putting some mappings to subMap) --
A --> VA
B --> VB
B1 --> VB1
B2 --> VB2
C --> VC
D --> VD
E --> VE

8. headMap(K toKey)

SortedMap<K,V> headMap(K toKey)
Returns a view of a portion of this SortedMap that includes mappings with keys less than toKey. (key < toKey).
The returned SortedMap is related to the current SortedMap. Changes on one SortedMap affect the other SortedMap and vice versa.
SortedMap_headMap_ex1.java
package org.o7planning.sortedmap.ex;

import java.util.SortedMap;
import java.util.TreeMap;

public class SortedMap_headMap_ex1 {

    public static void main(String[] args) {
        SortedMap<String, String> myMap = new TreeMap<>();

        myMap.put("A", "VA");
        myMap.put("B", "VB");
        myMap.put("C", "VC");
        myMap.put("D", "VD");
        myMap.put("D1", "VD1");
        myMap.put("E", "VE");

        // A Head Map (elements < "D1")
        SortedMap<String, String> headMap = myMap.headMap("D1");

        System.out.println(" -- headMap --");
        for (String s : headMap.keySet()) {
            System.out.println(s + " --> " + headMap.get(s));
        }
    }
}
Output:
-- headMap --
A --> VA
B --> VB
C --> VC
D --> VD

9. tailMap(K fromKey)

SortedMap<K,V> tailMap(K fromKey)
Returns a view of a portion of this SortedMap that includes mappings with key greater than or equal to fromKey. (key >= fromKey).
The returned SortedMap is related to the current SortedMap. Changes on one SortedMap affect the other SortedMap and vice versa.