SortedMap

SortedMap

In this lesson, we'll study the SortedMap interface. We'll explore new methods that appear in this interface, as well as the features of one implementation of SortedMap — TreeMap — and the differences between implementations, as well as their advantages compared to HashMap.

Let's see what the hierarchy of maps looks like. Pay special attention to the SortedMap interface and its TreeMap implementation — they are our focus today:

The SortedMap interface extends the Map interface. In many ways, it is similar to SortedSet (which in turn extends Set), since they both describe similar functionality for storing and using sorted values.

SortedSet works with and stores <TValue> objects, but SortedMap stores <TKey, TValue> pairs. It's a map that stores all its elements in ascending order of their keys.

The SortedMap interface extends Map. It adds the following methods:

TreeMap class

The TreeMap class is an implementation of the SortedMap interface. That is, TreeMap implements all the methods added by SortedMap as well as the standard ones from the Map interface.

You can create a TreeMap object using constructors like these:

• TreeMap(): creates an empty map implemented as a tree;

• TreeMap(Map<? extends TKey, ? extends TValue> map): creates a tree and adds all the elements from the input map;

• TreeMap(SortedMap<TKey, ? extends TValue> smap): creates a tree and adds all elements from the input sorted map;

• TreeMap(Comparator<? super TKey> comparator): creates an empty tree — the comparator will be used to sort all elements as they are subsequently added.

Here TKey is the type of the keys in the stored pairs, and TValue is the type of the values in the pairs stored in the TreeMap.

Comparator is pretty important for SortedMap/TreeMap. It establishes the rules for sorting — or ordering — our map. If we don't provide a comparator, then the natural ordering of our keys will be used when we create a SortedMap.

Adding elements to a TreeMap

Elements are added to a map as pairs using the put() method. The key is passed as the first argument, and the value is passed as the second. For example, suppose we want to create a list of students and their grades.

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

map.put("Anthony", 5);
map.put("Sara", 5);
map.put("Roxy", 5);
map.put("Jeff", 4);
map.put("Nick", 4);
map.put("Oliver", 3);
map.put("Oliver", 5);

System.out.println(map);

Result:

When we add a key-value pair, if the key already exists in the collection, then the old value is replaced by the new value. This behavior is illustrated in our example with two pairs that have the same key — ("Oliver", 3) and ("Oliver", 5).

Let's look at an example with a Comparator that we create. Suppose we want to store the elements sorted by the length of the key string. If the length of the keys is equal, then we will sort alphabetically (the natural ordering of strings):

class LengthComparator implements Comparator<String> {
  public int compare(String o1, String o2) {
    Integer lenghComparedResult = Integer.compare(o1.length(), o2.length());
    return lenghComparedResult != 0 ? lenghComparedResult : o1.compareTo(o2);
  }
}

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

lengthComparedMap.put("Jeff", 4);
lengthComparedMap.put("Oliver", 5);
lengthComparedMap.put("Roxy", 4);
lengthComaredMap.put("Jan", 4);

Here's the resulting sequence:

This behavior makes a TreeMap like a sorted array or list whose indices are words (String) instead of numbers.

SortedMap methods in the TreeMap class

1. If you need to get the key of the first student, you can use the firstKey() method:

   String firstKey = map.firstKey();
   	System.out.println("First key → " + firstKey);

   Result: First key → Anthony

2. If you need to get the key of the last student, you can use the lastKey() method:

   String lastKey = map.lastKey();
   System.out.println("Last key → " + lastKey);

   Result: Last Key → Jeff

3. Get all objects that come after the object with the key "Sara":

   Map<String, Integer> tailMap = map.tailMap("Sara");
            	System.out.println("tailMap: " + tailMap);

   Result: tailMap: {Sara=5, Jeff=4}

4. Get all objects that come before the object with the key "Nick":

   System.out.println("headMap: " + headMap);
    Map<String, Integer> headMap = map.headMap("Nick");

   Result: headMap: {Anthony=5}

5. Get all objects that come after the object with the key "Oliver" and come before the object with the key "Sara":

   Map<String, Integer> subMap = map.subMap("Oliver", "Sara");
   System.out.println("subMap: " + subMap);

   Result: subMap: {Oliver=5, Roxy=5}

Comparison of HashMap and SortedMap/TreeMap

Let's talk about how the elements are ordered and stored:

• Since HashMap does not give us any guarantees about order when iterating, the order may completely change when new elements are added.

• In TreeMap, the order is based on the "natural ordering" of the keys according to their compareTo() method (or a Comparator that we provide). Also, don't forget that TreeMap implements the SortedMap interface, which contains methods that depend on this sort order.

Now we turn to a consideration of performance and speed:

• HashMap is a map based on hashing keys. It can insert and get elements in O(1), constant time. To support this, the keys must implement hashCode() and equals().

• TreeMap is a tree-based map. Its insert and fetch operations take logarithmic time, i.e. O(log n), which depends on the number of elements in the map. This is necessary so that the elements have some sort of comparison mechanism provided by either our key or an external Comparator. This mechanism determines the iteration order.

And these factors help us decide which collections to use and when.

If we need to store values in a certain order, the choice is obvious — we need a SortedMap. Although it is a little slower than HashMap, it performs important tasks for us.

As mentioned earlier, SortedMap can give us the first (or last) key, or value, or key-value pair in our map, regardless of when that value was added. The HashMap implementation cannot do this.

For example, consider a map with keys (students' names) and values (their grades). Let's say we want to work with a list in reverse alphabetical order.

1.

SortedMap<String, Integer> sorted = new TreeMap<String,Integer>(Comparator.reverseOrder());
sorted.put("Anthony", 5);
sorted.put("Sara", 5);
sorted.put("Jeff", 4);

String firstKeyFromSortedMapVariant = sorted.firstKey();

Integer markFromSortedMap = sorted.get(firstKeyFromSortedMapVariant);
System.out.println(firstKeyFromSortedMapVariant + " - " + markFromSortedMap);

2.

HashMap<String, Integer> hash = new HashMap<String,Integer>();
hash.put("Anthony", 5);
hash.put("Sara", 5);
hash.put("Jeff", 4);

SortedSet<String> keySetOfHashMap = new TreeSet<String>(Comparator.reverseOrder());
// Or sort manually, storing elements in an array or list (preserving the insertion order)
keySetOfHashMap.addAll(hash.keySet());
String firstKeyFromHashMapVariant = keySetOfHashMap.first();


Integer markFromHashMap = hash.get(firstKeyFromHashMapVariant);
System.out.println(firstKeyFromHashMapVariant + " - " + markFromHashMap);

The example shows that using a HashMap makes the task more complicated, since HashMap guarantees neither the order of storage nor the order of obtaining elements from the map.