Features of TreeMap

If you're reading this article, you are most likely familiar with the Map interface and where can appropriately be applied. If not, then come here. Today we'll talk about the features of TreeMap's implementation, and more specifically, how it differs from HashMap and how to use it correctly.

Comparing TreeMap, HashMap, and LinkedHashMap

The most used implementation of the Map interface is HashMap. It's easy to use and guarantees quick access to data, so it is the best candidate for solving most problems. Most, but not all. Sometimes you need to store data in a structured way and be able to navigate through it. In this case, another implementation of the Map interface (TreeMap) comes to the rescue. TreeMap implements the NavigableMapinterface, which inherits SortedMap, which in turn inherits the Map interface. By implementing the NavigableMap and SortedMap interfaces, TreeMap receives additional functionality that is not available in HashMap, but it pays a price in terms of performance. There is also the LinkedHashMap class , which also allows you to store data in a specific order (the order in which you add it to the map). To understand the differences between these three classes, look at this table:

	HashMap	LinkedHashMap	TreeMap
Data ordering	Random. There is no guarantee that the order will be maintained over time.	In the order in which data is added	In ascending order or based on a specified comparator
Time complexity	O(1)	O(1)	O(log(n))
Implemented interfaces	Map	Map	NavigableMap SortedMap Map
Data structure	Buckets	Buckets	Red-black tree
Support for null key?	Yes	Yes	Yes, if a comparator is not used
Thread safe?	No	No	No

As you can see, these classes have a lot in common, but there are also several differences. Although the TreeMap class is the most versatile, it cannot always store null as a key. In addition, accessing the elements of a TreeMap takes the longest amount of time. So, if you don't need to store data in some sorted order, it is better to use HashMap or LinkedHashMap.

Red-black tree

You probably noticed that, under the hood, TreeMap uses a data structure called a red-black tree. Storing data in this structure is precisely what provides data ordering. So what kind of tree is this? Let's figure it out! Imagine that you need to store Number-String pairs. The numbers 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93, and 101 will be keys. If you store data in a traditional list and you need to find the element with key 101, then you will need to step through all 13 elements to find it. For 13 elements, this isn't a big deal, but when working with a million, we will have big problems. To solve these problems, programmers use slightly more complex data structures. This is where the red-black tree enters the stage! https://algorithmtutor.com/Data-Structures/Tree/Red-Black-Trees/

Search for an element begins at the root of the tree, which in our case is 61. Then we compare the node values with the value that we're looking for. If our value is less, then we go to the left; if it is greater, then we go to the right. This process repeats until we find the desired value or encounter an element whose value is null (a leaf of the tree). The colors red and black are used to simplify navigating and balancing the tree. There are rules that must always be observed when building a red-black tree:

• The root must be black.
• The leaves of the tree must be black.
• A red node must have two black child nodes.
• A black node can have child nodes of any color.
• A path from a node to its leaves must contain the same number of black nodes.
• New nodes are added to leaves.

If you consider Rules 3, 4 and 5 together, you can understand how node color lets us navigate the tree more quickly: a path through black nodes is always shorter than one through red nodes. Accordingly, the total size of the tree is determined by the number of black nodes, which is called the "black height". The red-black tree data structure is implemented in various programming languages. There are a lot of Java implementations on the Internet, so we won't linger here. Instead, let's continue getting to know TreeMap's functionality.

Methods that come from the SortedMap and NavigableMap interfaces

Like HashMap, TreeMap implements the Map interface, which means that TreeMap has all the methods that exist in HashMap. But TreeMap also implements the SortedMap and NavigableMap interfaces, and thus gains additional functionality from them. SortedMap is an interface that extends Map and adds methods relevant to a sorted dataset:

• firstKey(): returns the key of the first element in the map
• lastKey(): returns the key of the last element
• headMap(K end): returns a map that contains all the elements of the current map, from the beginning to the element with the key end
• tailMap(K start): returns a map that contains all the elements of the current map, from the start element to the end
• subMap(K start, K end): returns a map that contains all the elements of the current map, from the start element to the element with the key end.

NavigableMap is an interface that extends SortedMap and adds methods for navigating between elements of a map:

• firstEntry(): returns the first key-value pair
• lastEntry(): returns the last key-value pair
• pollFirstEntry(): returns and deletes the first pair
• pollLastEntry(): returns and deletes the last pair
• ceilingKey(K obj): returns the smallest key k that is greater than or equal to the key obj. If there is no such key, returns null
• floorKey(K obj): returns the largest key k that is less than or equal to the key obj. If there is no such key, returns null
• lowerKey(K obj): returns the largest key k that is less than the key obj. If there is no such key, returns null
• higherKey(K obj): returns the smallest key k that is larger than the key obj. If there is no such key, returns null
• ceilingEntry(K obj): similar to the ceilingKey(K obj) method, only returns a key-value pair (or null)
• floorEntry(K obj): similar to the floorKey(K obj) method, only returns a key-value pair (or null)
• lowerEntry(K obj): similar to the lowerKey(K obj) method, only returns a key-value pair (or null)
• higherEntry(K obj): similar to the higherKey(K obj) method, only returns a key-value pair (or null)
• descendingKeySet(): returns a NavigableSet containing all keys sorted in reverse order
• descendingMap(): returns a NavigableMap containing all pairs sorted in reverse order
• navigableKeySet(): returns a NavigableSet object containing all the keys in the order in which they are stored
• headMap(K upperBound, boolean incl): returns a map that contains pairs from the beginning to the upperBound element. The incl parameter indicates whether to include the upperBound element in the returned map
• tailMap(K lowerBound, boolean incl): functionality similar to the previous method, returns only pairs from lowerBound to the end
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): as with the previous methods, returns pairs from lowerBound to upperBound; the arguments lowIncl and highIncl indicate whether to include the boundary elements in the new map.

In addition to the usual constructors, TreeMap has another constructor that accepts an instance of a comparator. This comparator is responsible for the order in which elements are stored.

Examples of TreeMap

This abundance of extra methods may seem unnecessary, but they turn out to be much more useful than you might realize at first glance. Let's explore the following example together. Imagine that we work in the marketing department of a large company, and we have a database of people to whom we want to show ads. There are two details to keep in mind:

• We need to keep track of the number of impressions for each person
• The algorithm for displaying ads to minors is different.

Let's create a Person class, which will store all the relevant information about each person:

public class Person {
   public String firstName;
   public String lastName;
   public int age;

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

We implement the logic in the Main class:

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class Main {
   public static void main(String[] args) {
      TreeMap<Person, Integer> map = new TreeMap<>(new Comparator<Person>() {
          @Override
          public int compare(Person o1, Person o2) {
              return o1.age - o2.age;
          }
      });
      map.put(new Person("John", "Smith", 17), 0);
      map.put(new Person("Ivan", "Petrenko", 65), 0);
      map.put(new Person("Pedro", "Escobar", 32), 0);
      map.put(new Person("Shirley", "Hatfield", 14), 0);
      map.put(new Person("Abby", "Parsons", 19), 0);

      Person firstAdultPerson = map.navigableKeySet().stream().filter(person -> person.age>18).findFirst().get();

       Map<Person, Integer> youngPeopleMap = map.headMap(firstAdultPerson, false);
       Map<Person, Integer> adultPeopleMap = map.tailMap(firstAdultPerson, true);
       showAdvertisementToYoung(youngPeopleMap);
       showAdvertisementToAdult(adultPeopleMap);
   }

   public static void showAdvertisementToYoung(Map map) {}
   public static void showAdvertisementToAdult(Map map) {}
}

In the Main class, create a TreeMap, in which each key represents a specific person, and each value is the number of ad impressions this month. We pass the constructor a comparator that sorts people by age. We fill the map with arbitrary values. Now we want to get a reference to the first adult in our little data repository. We do this using the Stream API. Then we get two separate maps, which we pass to the methods that show ads. There are many, many ways we could have accomplished this task. The TreeMap class's arsenal of methods lets us create custom solutions for every need. You don't need to remember them all, because you can always use the documentation or tips from your IDE. That's all for now! I hope that the TreeMap class is clear to you now, and that you will apply it properly in solving practical coding tasks.