Introducing the TreeMap collection

One day at university, I needed to write code to sort my classmates' last names, which served as keys to their personal data, in ascending order. I spent a lot of time on this. But if I had known about the TreeMap class back then, I would have finished the task much faster.

What is a TreeMap? It is a dictionary-like data structure that stores elements as a key-value pairs, sorting them by key.

Where and how can it be used? Well, it would have been ideal for the same assignment with my classmates' last names. If I need to store values in ascending order, instead of writing my own sorting algorithm, all I have to do is create a TreeMap and put the values in it.

It sorts types such as Integer and String in ascending order. But if you want to put your own custom type in a TreeMap, then your class needs to implement the Comparable interface, so that it implements the compareTo() method, which indicates how to sort instances of your class.

public class Person implements Comparable<Person> {

    private String firstName;
    private String lastName;

    public Person(String firstName, String lastName) {
        this.firstName = firstName;
        this.lastName = lastName;
    }

    public String getFirstName() {
        return firstName;
    }

    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }

  …

    @Override
    public int compareTo(Person person) {
        return person.getFirstName().compareTo(firstName);
    }

    @Override
    public String toString() {
        return "Person{" +
                "firstName='" + firstName + '\'' +
                ", lastName='" + lastName + '\'' +
                '}';
    }
}

Let's override the compareTo() method so that it sorts the values by first name in reverse alphabetical order:

TreeMap map = new TreeMap<Person, String>();

map.put(new Person("AA","BB"), "aa");
map.put(new Person("BB","BB"), "aa");
map.put(new Person("DD","BB"), "aa");
map.put(new Person("CC","BB"), "aa");

The values will be stored in the following order:

Person{firstName='DD', lastName='BB'}
Person{firstName='CC', lastName='BB'}
Person{firstName='BB', lastName='BB'}
Person{firstName='AA', lastName='BB'}

The TreeMap class implements the NavigableMap interface, which in turn extends the SortedMap interface. This lets the TreeMap class use trees to store values in sorted order.

To put that in simple terms, a red-black tree is a data structure that stores values in the right subtree if they are greater than the root, and in the left subtree if they are less. This implementation can look up values in the structure very quickly.

A red-black tree is self-balancing, so it changes its structure as each new value is inserted. The value added first is initially considered the root, but another value can become the root during the balancing process.

Well, now you know what TreeMap is and how it works.

Remember that TreeMap can only store objects whose class implements the Comparable interface and overrides the compareTo() method.

But what if we are using third-party classes loaded from various libraries and cannot implement Comparable in them? There is a solution for this: write your own Comparator.

Comparator is an interface that has a compare() method. We can use it to compare objects and store them in a TreeMap.

Comparator<Person> comparator = new Comparator<Person>() {

    @Override
    public int compare(Person person1, Person person2) {
        return person1.getFirstName().compareTo(person2.getFirstName());
    }
};


TreeMap map = new TreeMap<Person, String>(comparator);

In this example, we created a custom Comparator and passed a TreeMap to the class.

Starting in Java 8, we can write this using a lambda expression:

TreeMap map = new TreeMap<Person, String>((Person person1, Person person2) -> person1.getFirstName().compareTo(person2.getFirstName()));

In other words, in order to store values in a TreeMap, you need to specify how to sort them. There are two ways to do this: implement Comparable or implement your own Comparator.

But what if we need to put null into a TreeMap as a key? HashMap lets you do this. Yes, but how does TreeMap handle this?

TreeMap map = new TreeMap<Person, String>();
map.put (null, "Person");

Running this code gives us an error:

The problem is that internally the TreeMap class compares values using the compareTo() method. You can certainly pass in a null value in and the code will compile. But at runtime you'll get an error, because the method will be called on a null value, causing a NullPointerException to be thrown.

Comparison of HashMap and TreeMap

Unlike TreeMap, HashMap lets you store null as a key. The structure has a specific place for all null keys. HashMap is able to store null keys because it determines where they go based on their hash value, and calculating the hash value does not which require comparisons. So all null keys have their place.

There you have it — now you know what to use when you need to store values in sorted order, and how to set the rules for sorting.