Introduction

A TreeMap is a Red-Black Tree based implementation of a NavigableMap. The entries of the map are sorted according to the natural ordering of the keys (the keys implement the Comparable interface) or by a explicitly passed Comparator during the TreeMap creation time. In this post, we will look at TreeMap in Java, its important parent classes and the methods offered by them with examples.

Class hierarchy of TreeMap

TreeMap is one of the implementations of NavigableMap. A NavigableMap is a SortedMap.

A NavigableMap is a SortedMap extended with navigation methods that return the closest matches for given search targets. It is used for navigating or locating entries and not for traversing.

A SortedMap is just a Map that further provides a total ordering on its keys. The map is ordered either by the natural ordering of the map’s keys or by a Comparator provided at the sorted map creation time.

TreeMap in Java

A TreeMap offers log(n) time cost for insertion, searching and deletion operations.

A very important thing to consider when using a SortedMap is ordering. The ordering must be consistent with the equals method if the sorted map is to correctly implement the Map interface’s contract. A normal Map interface is defined in terms of the equals method, but a sorted map performs all the key operations using either the compareTo method if the keys implement Comparable or the compare method when passed an explicit Comparator. When the ordering imposed is not consistent with equals then the sorted map fails to obey the general contract of a Map. We will revisit this part towards the end of the post.

TreeMap construction - Using Comparable keys

We will construct a simple TreeMap with String as keys and Integer as value. We do not pass a comparator and let the entries of the map be ordered as per the String’s (key’s) natural ordering (lexicographical ordering)

NavigableMap<String, Integer> navigableMap = new TreeMap<>();
navigableMap.put("Joe", 78);
navigableMap.put("Andrew", 54);
navigableMap.put("Zack", 61);
navigableMap.put("Michael", 94);
navigableMap.put("Kyle", 53);

Since a TreeMap is a NavigableMap which is a SortedMap, we will explore TreeMap by looking at the methods of a SortedMap and then a NavigableMap.

SortedMap methods

Basic methods

A sorted map has the methods firstKey and lastKey to access the first and the last keys of the map. Apart from this, it has a normal map’s methods like keySet, entrySet, and values.

System.out.println(navigableMap.firstKey());  //Andrew
System.out.println(navigableMap.lastKey());   //Zack
System.out.println(navigableMap.keySet());    //[Andrew, Joe, Kyle, Michael, Zack]
System.out.println(navigableMap.values());    //[54, 78, 53, 94, 61]
System.out.println(navigableMap.entrySet());  //[Andrew=54, Joe=78, Kyle=53, Michael=94, Zack=61]

It can now be easily observed how the entries are stored and accessed. The entries are sorted by the name (String)

HeadMap, TailMap and SubMap

A SortedMap has the following methods

  • headMap(toKey) - This takes a key(toKey) and returns a view of the portion of the map whose keys are strictly less than the passed key (hence the passed key is exclusive)
  • tailMap(fromKey) - This takes a key(fromKey) and returns a view of the portion of the map whose keys are greater than or equal to the passed key (hence the passed key is inclusive)
  • subMap(fromKey, toKey) - This accepts two keys, a fromKey and a toKey. It returns a view of the portion of the map whose keys range from fromKey(inclusive) to toKey(exclusive)

The returned map in all the above cases is backed up by the original map. So, the changes made to the original map is reflected in the view and vice versa.

System.out.println(navigableMap.headMap("Joe")); //{Andrew=54}
System.out.println(navigableMap.tailMap("Michael")); //{Michael=94, Zack=61}
System.out.println(navigableMap.subMap("Joe", "Michael")); //{Joe=78, Kyle=53}
System.out.println(navigableMap.subMap("Joe", "Joe")); //{}

Ceil, Floor, High, and Low methods

  • ceilingKey(key) - It returns the least key greater than or equal to the given key
  • ceilingEntry(key) - Returns the key-value entry associated with the least key greater than or equal to the given key.
  • floorKey(key) - It returns the greatest key less than or equal to the given key.
  • floorEntry(key) - Returns the key-value entry associated with the greatest key less than or equal to the given key.
  • higherKey(key) - It returns the least key strictly greater than the given key.
  • higherEntry(key) - Returns the key-value entry associated with the least key strictly greater than the given key.
  • lowerKey(key) - It returns the greatest key strictly less than the given key.
  • lowerEntry(key) - Returns the key-value entry associated with the greatest key strictly less than the given key.

These might appear to be confusing at first. Have a look at the examples below to get a clarification.

System.out.println(navigableMap.ceilingKey("Joe")); //Joe
System.out.println(navigableMap.ceilingEntry("Joe")); //Joe=78

System.out.println(navigableMap.higherKey("Joe")); //Kyle
System.out.println(navigableMap.higherEntry("Joe")); //Kyle=53
System.out.println(navigableMap.higherKey("Zack")); //null

System.out.println(navigableMap.floorKey("Joe")); //Joe
System.out.println(navigableMap.floorEntry("Joe")); //Joe=78

System.out.println(navigableMap.lowerKey("Joe")); //Andrew
System.out.println(navigableMap.lowerEntry("Joe")); //Andrew=54
System.out.println(navigableMap.lowerKey("Andrew")); //null

Overloaded HeadMap, TailMap and SubMap methods

In addition to the headMap, tailMap and subMap methods we saw as part of the SortedMap, there are overloaded version of these to indicate whether or not to include the fromKey and toKey. As we saw earlier, the toKey is exclusive and the fromKey is always inclusive. Passing a flag that reverses this produces different results.

System.out.println(navigableMap.headMap("Joe", true)); //{Andrew=54, Joe=78}
System.out.println(navigableMap.tailMap("Michael", false)); //{Zack=61}
System.out.println(navigableMap.subMap("Joe", true, "Michael", true)); //{Joe=78, Kyle=53, Michael=94}
System.out.println(navigableMap.subMap("Joe", false, "Michael", true)); //{Kyle=53, Michael=94}

Descending Map

It has a method called descendingMap that returns a reverse order view of the original map. The returned map is backed up by the original map.

System.out.println(navigableMap.descendingMap()); //{Zack=61, Michael=94, Kyle=53, Joe=78, Andrew=54}

Methods for accessing and removing first and last entries

The methods firstEntry and lastEntry returns the first and the last entry in the map. Methods pollFirstEntry and pollLastEntry are used to return and remove the first and the last entry respectively.

System.out.println(navigableMap.firstEntry()); //Andrew=54
System.out.println(navigableMap.lastEntry()); //Zack=61
System.out.println(navigableMap.pollFirstEntry()); //Andrew=54
System.out.println(navigableMap.pollLastEntry()); //Zack=61
System.out.println(navigableMap); //{Joe=78, Kyle=53, Michael=94}

TreeMap construction - Using a custom comparator

As mentioned earlier, we can also pass a custom comparator when creating a TreeMap (even if the keys implement Comparable). In this case, the passed Comparator will be used to order the map entries.

Let us create a TreeMap with same data but by ordering it by the String’s (name’s) length rather than ordering it lexicographically. In case of a tie (two Strings having same length), we will sort them by String’s natural order.

navigableMap = new TreeMap<>(Comparator.comparingInt(String::length)
                .thenComparing(Comparator.naturalOrder()));
navigableMap.put("Joe", 78);
navigableMap.put("Andrew", 54);
navigableMap.put("Zack", 61);
navigableMap.put("Michael", 94);
navigableMap.put("Kyle", 53);
System.out.println(navigableMap); //{Joe=78, Kyle=53, Zack=61, Andrew=54, Michael=94}

Comparator utility method comparing is used to define a comparator. If you want to learn more on this, check out the Comparator comparing post.

Danger of inconsistent ordering

We briefly touched upon the point of ordering being consistent with equals. We will now see the problem when this is violated.

In the above comparator, if we remove the tie-breaking decision of natural ordering when we have two Strings of equal length, we will have a TreeMap that violates a Map’s contract.

navigableMap = new TreeMap<>(Comparator.comparingInt(String::length));

Now, if we add the above elements into the map and print the map, it won’t have an entry for Kyle but Kyle value would be stored against Zack. The map would look like.

{Joe=78, Zack=53, Andrew=54, Michael=94}

This is because though the keys Zack and Kyle are not equal (as per the equals method), the Comparator considered them to be the same. Hence, when we added Kyle, and internally when it compares it with Zack, the compare method would return 0. Thus, they are considered the same by the TreeMap and it replaced the value for Kyle against Zack (It is like performing a repeated put with different value for the same key)

If we were to add these five entries into a HashMap, we would have five entries because a HashMap uses equals.

Conclusion

In this post, we looked at the TreeMap in Java. We also learnt about a NavigableMap and a SortedMap. A rich set of examples were provided demonstrating the various methods available.

Want to learn how a hash map works in java, then check out this post.