Java TreeMap And Its’ Little-Known Features

What is Java TreeMap?

Java TreeMap is a collection that implements from the NavigableMap interface. It has been available since JDK 1.2. In its’ essence TreeMap is an implementation of Red-Black tree. Red-Black tree is a self-balancing binary tree.

TreeMap in Java stores key-value pairs. In addition, the keys are sorted by their natural ordering. This means that numbers will be sorted as 1, 2, 3 etc. and strings will be sorted as a, b, c etc. You can also define your own sorting for the keys by providing a comparator during the creation of a TreeMap.

To point out, methods get, put, containsKey and remove have the time complexity of log(n). This is considered to be good.

(Big-O chart taken from here).

Note: Java TreeMap is not synchronized. We can achieve a synchronized version of a TreeMap by wrapping it with Collections.synchronizedSortedMap:

Map<Character, String> synchronizedMap = 
        Collections.synchronizedSortedMap(new TreeMap<>());

How to use Java TreeMap?

TreeMap in Java provides various methods to retrieve and manipulate the entries it holds. It offers several different operations from other maps like HashMap. This includes for example finding ceiling and floor for a key. You can find the whole list of methods in its’ documentation.

Now, lets’ take a look at how to create a TreeMap in Java. Then we move on to the little-known features of it. And finally we’ll also cover the more common ones.

Creating Java TreeMap

By default the keys in TreeMap are sorted according to their natural ordering. In the example we have a TreeMap that stores letters as keys and animals as values.

// Creating a map
TreeMap<Character, String> animalsByLetter = new TreeMap<>();

// Add a letter and corresponding animal to the map
animalsByLetter.put('s', "sebra");
animalsByLetter.put('m', "monkey");
animalsByLetter.put('p', "panda");
animalsByLetter.put('c', "cat");

// Print out all animals in the map
animalsByLetter.entrySet().forEach(animal ->
        System.out.println(
               "Letter: " + animal.getKey() + 
               ", Animal: " + animal.getValue())
);

Output:

Letter: c, Animal: cat
Letter: m, Animal: monkey
Letter: p, Animal: panda
Letter: s, Animal: sebra

Custom sorting of TreeMap

To define custom sorting we can use a Comparator when creating a TreeMap. In the following example we are creating a TreeMap that has keys in the reversed order.

// Creating a map in reverse order by providing a Comparator
TreeMap<Character, String> animalsByLetter = 
        new TreeMap<>(Collections.reverseOrder());

// Add a letter and corresponding animal to the map
animalsByLetter.put('s', "sebra");
animalsByLetter.put('m', "monkey");
animalsByLetter.put('p', "panda");
animalsByLetter.put('c', "cat");

// Print out all animals in the map
animalsByLetter.entrySet().forEach(animal ->
        System.out.println(
                "Letter: " + animal.getKey() + 
                ", Animal: " + animal.getValue())
);

Output:

Letter: s, Animal: sebra
Letter: p, Animal: panda
Letter: m, Animal: monkey
Letter: c, Animal: cat

First and last key (or entry) in TreeMap

One of the little-known features of Java TreeMap is the ability to find the first and last key (or entry) in a map. To do this we can use the methods: firstKey, firstEntry, lastKey, lastEntry. In the example we cover finding the first and last keys:

// Find first key
System.out.println("First key: " + animalsByLetter.firstKey());

// Find last key
System.out.println("Last key: " + animalsByLetter.lastKey());

Output:

First key: c
Last key: s

Ceiling and floor for a key (or entry) in TreeMap

Ceiling returns the least key (or entry) that is greater than or equal to the specified key. Floor returns the greatest key (or entry) that is less or equal to the specified key. If no such key exists, it returns null.

In the example we cover finding the ceiling and floor for a key by using the methods ceilingKey and floorKey. For map entry we could use: ceilingEntry, floorEntry.

// Find ceiling value for letter r
System.out.println("Ceiling value: " + animalsByLetter.ceilingKey('r'));

// Find floor value for letter r
System.out.println("Floor value: " + animalsByLetter.floorKey('r'));

Output:

Ceiling value: s
Floor value: p

Higher and lower key (or entry) in TreeMap

Higher key (or entry) returns the greatest key (or entry) for the specified key. Lower key (or entry) returns the greatest key (or entry) that is less than the specified key. When no key is found, it returns null.

For keys we can use methods: higherKey, lowerKey. For entries: higherEntry, lowerEntry.

// Find higher key for letter m
System.out.println("Higher key: " + animalsByLetter.higherKey('m'));

// Find lower key for letter m
System.out.println("Lower key: " + animalsByLetter.lowerKey('m'));

Output:

Higher key: p
Lower key: c

Head and tail for a key in TreeMap

Head for map returns the entries that are less than the specified key. Tail returns entries that are equal or greater to the given key.

// Get key-value pairs before letter p
System.out.println("Head map: " + animalsByLetter.headMap('p'));

// Get key-value pairs equal and after letter p
System.out.println("Tail map: " + animalsByLetter.tailMap('p'));

Output:

Head map: {c=cat, m=monkey}
Tail map: {p=panda, s=sebra}

Retrieve values from TreeMap

For getting values from TreeMap we can use the get method by specifying a key. Another option is to use getOrDefault that returns a default value when the key doesn’t exist in the map.

// Get animal with letter S
String animalWithLetterS = animalsByLetter.get('s');

// Get animal with letter T or return a default animal
String animalWithLetterT = animalsByLetter.getOrDefault('t', "tiger");

System.out.println("Animal starting with letter s: " + animalWithLetterS);
System.out.println("Animal starting with letter t: " + animalWithLetterT);

Output:

Animal starting with letter s: sebra
Animal starting with letter t: tiger

Check if key or value exists in TreeMap

To check if a key exists in a TreeMap we can use the containsKey method. For values exists the containsValue method.

System.out.println(
        "Letter exists in the map: " + 
        animalsByLetter.containsKey('s')
);
System.out.println(
        "Animal exists in the map: " + 
        animalsByLetter.containsValue("sebra")
);

Output:

Letter exists in the map: true
Animal exists in the map: true

Remove entry from TreeMap

To remove an entry from a TreeMap we can use the remove method:

// Remove entry from map by key
animalsByLetter.remove('s');

Poll first and last entry from TreeMap

Poll will return and remove an entry from the map. We can use methods pollFirstEntry and pollLastEntry for that. If the map is empty, the method returns null.

System.out.println(
        "Polled first entry: " + animalsByLetter.pollFirstEntry());
System.out.println(
        "Polled last entry: " + animalsByLetter.pollLastEntry());

Output:

Polled first entry: c=cat
Polled last entry: p=panda

Conclusion

Java TreeMap is an unsynchronized collection that by default has natural ordering for its’ keys. We can also define our own ordering for the keys by using a comparator. The time complexity for a TreeMap is log(n) which is considered to be very good. We also covered various little-known and more commonly known features of Java TreeMap.

If you liked this blog post, don’t forget to subscribe (if you already haven’t 🙂 ) so you wouldn’t miss the next post!