Features of TreeMap in Java

If you're reading this article, chances are you're familiar with the Map interface and its uses. If not, then here you go. Today we will talk about the implementation features of TreeMap, and more specifically, how it differs from HashMap and how to use it correctly.

Comparison of TreeMap, HashMap and LinkedHashMap

The most commonly used implementation of the Map interface is HashMap . It's easy to use and guarantees fast access to data, making it the best candidate for most tasks. Most, but not all. Sometimes it is necessary to store data in a structured form with the ability to navigate through it. In this case, another implementation of the Map interface comes to the rescue - TreeMap . TreeMap implements the NavigableMap interface , which inherits from SortedMap , which in turn inherits from the Map interface . By implementing the NavigableMap and SortedMap interfaces , TreeMap gains additional functionality that HashMap does not , but this comes at a cost in performance. There is also a LinkedHashMap class , which also allows you to store data in a certain order - in the order they were added. To help you understand the differences between these three classes, look at this table: As you can see, these classes have a lot in common, but there are also a few differences. Although the class TreeMapis the most multifunctional, it cannot always be stored nullas a key. In addition, the access time to TreeMap elements will be the longest. Therefore, if you do not need to store data in sorted form, it is better to use HashMapor LinkedHashMap.

Red-ebony tree

As you probably noticed, under the hood TreeMapit uses a data structure called a red-black tree. It is the storage of data in this structure that ensures the order in which the data is stored. What is this tree? 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, 101 will be the keys. If you store data in a traditional list and need to find an element with key 101, you will need to iterate through all 13 elements to find it. For 13 elements this is not critical; when working with a million we will have big troubles. To solve such problems, programmers use slightly more complex data structures. Therefore, meet the red-black tree!

https://algorithmtutor.com/Data-Structures/Tree/Red-Black-Trees/

The search for the required element starts from the root of the tree, in our case it is 61. Next, a comparison is made with the required value. If our value is less, we go to the left, if it is more, we go to the right. This happens until we find the required value or hit an element with a value null(a leaf of a tree). Red and black colors are used to make the tree easier to navigate and balance. There are rules that must always be followed when building a red-black tree:

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

If you look at rules 3, 4, and 5 together, you can understand how coloring nodes speeds up navigation through the tree: the path through black nodes is always shorter than through red ones. Therefore, the total size of the tree is determined by the number of black nodes, and this size is called “black height”. The red-black tree is implemented in different programming languages. There are a lot of implementations for Java on the Internet, so we won’t dwell on it for long, but will continue to get acquainted with the functionality TreeMap.

Methods derived from the SortedMap and NavigableMap interfaces

Like HashMap, TreeMapit implements the interface Map, which means that it TreeMaphas all the methods that HashMap. But in addition, TreeMapit implements interfaces SortedMapand NavigableMap, obtaining additional functionality from them. SortedMap— an interface that extends Mapand adds methods relevant to a sorted data set:

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

NavigableMap— an interface that extends SortedMapand adds methods for navigating between map elements:

• firstEntry(): returns the first key-value pair;
• lastEntry(): returns the last key-value pair;
• pollFirstEntry(): returns and removes the first pair;
• pollLastEntry(): returns and removes the last pair;
• ceilingKey(K obj): Returns the smallest key k that is greater than or equal to 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 key obj. If there is no such key, returns null;
• lowerKey(K obj): Returns the largest key k that is smaller than key obj. If there is no such key, returns null;
• higherKey(K obj): Returns the smallest key k that is greater than key obj. If there is no such key, returns null;
• ceilingEntry(K obj): similar to the ceilingKey(K obj) method, but returns a key-value pair (or null);
• floorEntry(K obj): similar to the floorKey(K obj) method, but returns a key-value pair (or null);
• lowerEntry(K obj): similar to the lowerKey(K obj) method, but returns a key-value pair (or null);
• higherEntry(K obj): similar to the higherKey(K obj) method, but 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 storage order;
• headMap(K upperBound, boolean incl): returns a map that contains pairs from the beginning to the upperBound element. The incl argument specifies whether the upperBound element should be included in the returned map;
• tailMap(K lowerBound, boolean incl): functionality is similar to the previous method, only pairs from lowerBound to the end are returned;
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): As in the previous methods, pairs from lowerBound to upperBound are returned, the arguments lowIncl and highIncl specify whether to include the boundary elements in the new map.

In the implementation itself TreeMap, in addition to the constructors we are familiar with, one more is added, which accepts an instance of the comparator. This comparator will be responsible for the order in which the elements are stored.

Examples of using TreeMap

Such an abundance of additional methods may seem unnecessary, but very often they turn out to be much more useful than it initially seemed. Let's look at this example with you. 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 advertising. There are two nuances to this:

• we need to keep track of the number of impressions to each person;
• The algorithm for displaying advertising to minors is different.

Let's create a class Personthat will store all the information available to us about a 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 class Main:

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<>(Comparator.comparingInt(o -> o.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("Radion", "Pyatkin", 14), 0);
      map.put(new Person("Sergey", "Vashkevich", 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 class Mainwe create TreeMap, where keyis a specific person, and valueis the number of ad impressions this month. In the constructor we pass a comparator that will sort people by age. Fill with maprandom values. Now we need to get a reference to the first adult in our mini data store. We do this using the Stream API. After this, we get two independent maps, which we pass to the methods that display advertising. There are many, many ways in which this problem could be solved. The class's arsenal of methods TreeMapallows you to invent solutions to suit every taste. It is not necessary to remember them all, because you can always use the documentation or hints from the development environment. That's all! I hope the class is now TreeMapclear to you, and you will find precise application for it in solving practical problems.