TreeMap in Java is also one of the implementation of the Map interface like HashMap and LinkedHashMap. How TreeMap differs from these other implementations is that the elements in TreeMap are sorted on keys.
The elements in TreeMap are ordered according to the natural ordering of its keys, which is the default sort ordering or a comparator can be provided at map creation time to provide custom ordering (We'll see an example a little later).
How TreeMap is implemented in Java
TreeMap class in Java implements the NavigableMap interface and extends the AbstractMap class.
TreeMap is a Red-Black tree based NavigableMap implementation. This implementation provides guaranteed
log(n) time cost for the containsKey, get, put and remove operations.
Some of the important points about TreeMap in Java which are discussed in this post are as follows-
- TreeMap in Java is a Red-Black tree based NavigableMap implementation.
- TreeMap stores its elements in sorted order and sorting is done on keys. By default elements are sorted using their
natural ordering.
- If you want to sort elments in TreeMap in any other order then you will have to provide a Comparator.
- TreeMap doesn’t allow null as key though other Map implementation like HashMap and LinkedHashMap do allow one key as null.
- Key in the TreeMap should be unique otherwise the previous stored value for the same key will be overwritten.
Duplicate values are allowed though.
- TreeMap in Java is not synchronized so it is not thread safe. If TreeMap is accessed concurrently by multiple threads
and at least one of the threads modifies the map structurally, then the TreeMap must be synchronized externally.
- The iterators returned by the iterator method of the collections returned by all of the TreeMap's "collection view methods"
are fail-fast. If the map is structurally modified at any time after the iterator is created, in any way except through the
iterator's own remove method, the iterator will throw a ConcurrentModificationException.
Java TreeMap Constructors
There are four constructors in the TreeMap class in Java.
- TreeMap()- Constructs a new, empty tree map, using the natural ordering of its keys.
- TreeMap(Comparator<? super K> comparator)- Constructs a new, empty tree map, ordered according to the
given comparator.
- TreeMap(Map<? extends K,? extends V> m)- Constructs a new tree map containing the same mappings as the
given map, ordered according to the natural ordering of its keys.
- TreeMap(SortedMap<K,? extends V> m)- Constructs a new tree map containing the same mappings and using the
same ordering as the specified sorted map.
Java TreeMap creation and element insertion example
public class TreeMapDemo {
public static void main(String[] args) {
Map<String, String> cityTemperatureMap = new TreeMap<String, String>();
// Storing elements
cityTemperatureMap.put("Delhi", "24");
cityTemperatureMap.put("Mumbai", "32");
cityTemperatureMap.put("Chennai", "35");
cityTemperatureMap.put("Bangalore", "22" );
cityTemperatureMap.put("Kolkata", "28");
cityTemperatureMap.put("Chennai", "36");
// iterating the map
for(Map.Entry<String, String> me : cityTemperatureMap.entrySet()){
System.out.println(me.getKey() + " " + me.getValue());
}
}
}
Output
Bangalore 22
Chennai 36
Delhi 24
Kolkata 28
Mumbai 32
It can be seen that the elements in TreeMap are sorted according to the natural ordering of its keys which is ascending for String.
Also note that though Chennai is added twice but it is stored only once as trying to store the same key twice
will result in overwriting of the old value with the new value (as the calculated hash will be the same
for the keys). Thus the last one is displayed while iterating the values.
TreeMap doesn't allow null
Though HashMap and LinkedHashMap allow one null as key, TreeMap in Java doesn't allow null as key. Any attempt
to add null in a TreeMap will result in a NullPointerException.
public class TreeMapDemo {
public static void main(String[] args) {
Map<String, String> cityTemperatureMap = new TreeMap<String, String>();
// Storing elements
cityTemperatureMap.put("Delhi", "24");
cityTemperatureMap.put("Mumbai", "32");
cityTemperatureMap.put("Chennai", "35");
cityTemperatureMap.put("Bangalore", "22" );
cityTemperatureMap.put("Kolkata", "28");
// Null key
cityTemperatureMap.put(null, "36");
// iterating the map
for(Map.Entry<String, String> me : cityTemperatureMap.entrySet()){
System.out.println(me.getKey() + " " + me.getValue());
}
}
}
Output
Exception in thread "main" java.lang.NullPointerException
at java.util.TreeMap.put(Unknown Source)
at org.netjs.prog.TreeMapDemo.main(TreeMapDemo.java:17)
Sorting elements in different order in TreeMap
As already mentioned by default elements are stored in TreeMap using natural ordering. If you want to sort
TreeMap is descending order (reverse order) then you need to provide your own Comparator at map creation time. Let's see an
example where we sort the TreeMap of Strings in descending order of its keys.
public class TreeMapDemo {
public static void main(String[] args) {
Map<String, String> cityTemperatureMap = new TreeMap<String, String>(new TreeComparator());
// Storing elements
cityTemperatureMap.put("Delhi", "24");
cityTemperatureMap.put("Mumbai", "32");
cityTemperatureMap.put("Chennai", "35");
cityTemperatureMap.put("Bangalore", "22" );
cityTemperatureMap.put("Kolkata", "28");
// iterating the map
for(Map.Entry<String, String> me : cityTemperatureMap.entrySet()){
System.out.println(me.getKey() + " " + me.getValue());
}
}
}
//Comparator class
class TreeComparator implements Comparator<String>{
@Override
public int compare(String str1, String str2) {
return str2.compareTo(str1);
}
}
Output
Mumbai 32
Kolkata 28
Delhi 24
Chennai 35
Bangalore 22
Here note that a Custom Comparator is implemented with the logic to sort objects in reverse order. That Comparator is passed
in the constructor of the TreeMap at map creation time .
TreeMap is not synchronized
TreeMap in Java is not thread safe. In case we need to Synchronize it, it should be synchronized externally.
That can be done using the Collections.synchronizedSortedMap method.
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
TreeMap class' iterator is fail-fast
The iterators returned by TreeMap in Java are fail-fast, if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException.
TreeMap iteration example
In the example we’ll get the Set view of the mapped entries using the entrySet() method. While iterating that Set we’ll try
to remove an element from the TreeMap using the Map's remove() method (not the iterator's remove method) which means a
structural modification and results in ConcurrentModificationException being thrown.
public class TreeMapItr {
public static void main(String[] args) {
Map<String, String> langMap = new TreeMap<String, String>();
// Storing (key, value) pair to HashMap
langMap.put("ENG", "English");
langMap.put("NLD", "Dutch");
langMap.put("ZHO", "Chinese");
langMap.put("BEN", "Bengali");
langMap.put("ZUL", "Zulu");
langMap.put("FRE", "French");
// Collection view of the TreeMap
Set<Map.Entry<String, String>> langSet = langMap.entrySet();
Iterator<Map.Entry<String, String>> itr = langSet.iterator();
while (itr.hasNext()) {
Map.Entry<String, String> entry = itr.next();
System.out.println("Key is " + entry.getKey() + " Value is " + entry.getValue());
// removing value using TreeMap's remove method
if(entry.getKey().equals("NLD")){
langMap.remove(entry.getKey());
}
}
}
}
Output
Key is BEN Value is Bengali
Key is ENG Value is English
Key is FRE Value is French
Key is NLD Value is Dutch
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.TreeMap$PrivateEntryIterator.nextEntry(TreeMap.java:1207)
at java.util.TreeMap$EntryIterator.next(TreeMap.java:1243)
at java.util.TreeMap$EntryIterator.next(TreeMap.java:1238)
at org.netjs.examples.impl.TreeMapItr.main(TreeMapItr.java:23)
If iterator's remove method is used to remove an element from TreeMap while it is iterated then the ConcurrentModificationException
is not thrown.
public class TreeMapItr {
public static void main(String[] args) {
Map<String, String> langMap = new TreeMap<String, String>();
// Storing (key, value) pair to HashMap
langMap.put("ENG", "English");
langMap.put("NLD", "Dutch");
langMap.put("ZHO", "Chinese");
langMap.put("BEN", "Bengali");
langMap.put("ZUL", "Zulu");
langMap.put("FRE", "French");
// Collection view of the TreeMap
Set<Map.Entry<String, String>> langSet = langMap.entrySet();
Iterator<Map.Entry<String, String>> itr = langSet.iterator();
while (itr.hasNext()) {
Map.Entry<String, String> entry = itr.next();
// removing value using iterator's remove method
if(entry.getKey().equals("NLD")){
itr.remove();
}
}
for(Map.Entry<String, String> lang : langMap.entrySet()) {
System.out.println("Key- " + lang.getKey() +
" Value- " + lang.getValue());
}
}
}
Output
Key- BEN Value- Bengali
Key- ENG Value- English
Key- FRE Value- French
Key- ZHO Value- Chinese
Key- ZUL Value- Zulu
As you can see element from TreeMap is removed when iterator's remove() metod is used and ConcurrentModificationException is not thrown.
Reference:
https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/util/TreeMap.html
That's all for this topic TreeMap in Java With Examples. If you have any doubt or any suggestions to make please drop a comment. Thanks!
Related Topics
-
How HashMap Works Internally in Java
-
How to Sort Elements in Different Order in TreeSet
-
How to Loop Through a Map in Java
-
HashMap Vs LinkedHashMap Vs TreeMap in Java
-
Java Collections Interview Questions And Answers
You may also like-
-
Abstraction in Java
-
Type Casting in Java With Conversion Examples
-
EnumSet in Java
-
How to Remove Duplicate Elements From an ArrayList in Java
-
Race Condition in Java Multi-Threading
-
Java ThreadLocal Class With Examples
-
Functional Interface Annotation in Java
-
Spring Setter Based Dependency Injection
