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 .
- To read more about Comparable and Comparator refer this post Difference between Comparable and Comparator
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(...));
- To see an example of how to synchronize an ArrayList refer How and why to synchronize ArrayList in Java
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.
- To read more about fail-fast and fail-safe iterators refer this post fail-fast Vs fail-safe iterator in Java
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
You may also like-
No comments:
Post a Comment