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.
![Features of TreeMap - 1]()
By implementing the
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 ![Features of TreeMap - 3]()
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 ![Features of TreeMap - 4]()

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 theNavigableMap
interface, which inherits SortedMap
, which in turn inherits the Map interface.

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 |
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!
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.

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 theSortedMap
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 maplastKey()
: returns the key of the last elementheadMap(K end)
: returns a map that contains all the elements of the current map, from the beginning to the element with the key endtailMap(K start)
: returns a map that contains all the elements of the current map, from the start element to the endsubMap(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.
firstEntry()
: returns the first key-value pairlastEntry()
: returns the last key-value pairpollFirstEntry()
: returns and deletes the first pairpollLastEntry()
: returns and deletes the last pairceilingKey(K obj)
: returns the smallest key k that is greater than or equal to the key obj. If there is no such key, returns nullfloorKey(K obj)
: returns the largest key k that is less than or equal to the key obj. If there is no such key, returns nulllowerKey(K obj)
: returns the largest key k that is less than the key obj. If there is no such key, returns nullhigherKey(K obj)
: returns the smallest key k that is larger than the key obj. If there is no such key, returns nullceilingEntry(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 orderdescendingMap()
: returns a NavigableMap containing all pairs sorted in reverse ordernavigableKeySet()
: returns a NavigableSet object containing all the keys in the order in which they are storedheadMap(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 maptailMap(K lowerBound, boolean incl)
: functionality similar to the previous method, returns only pairs from lowerBound to the endsubMap(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.
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.
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.
GO TO FULLL VERSION