Saturday, December 8, 2018

TreeMap in Java With Examples

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-

  1. TreeMap in Java is a Red-Black tree based NavigableMap implementation.
  2. TreeMap stores its elements in sorted order and sorting is done on keys. By default elements are sorted using their natural ordering.
  3. If you want to sort elments in TreeMap in any other order then you will have to provide a Comparator.
  4. TreeMap doesn’t allow null as key though other Map implementation like HashMap and LinkedHashMap do allow one key as null.
  5. Key in the TreeMap should be unique otherwise the previous stored value for the same key will be overwritten. Duplicate values are allowed though.
  6. 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.
  7. 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

  1. How HashMap internally works in Java
  2. How to Sort elements in different order in TreeSet
  3. How to loop through a map in Java
  4. HashMap Vs LinkedHashMap Vs TreeMap in Java
  5. Java Collections Interview Questions And Answers

You may also like-

  1. Abstraction in Java
  2. Type Casting in Java
  3. EnumSet in Java
  4. How to remove duplicate elements from an ArrayList in Java
  5. Race condition in Java multi-threading
  6. ThreadLocal class in Java
  7. Functional Interface Annotation in Java
  8. Setter-based dependency injection in Spring

No comments:

Post a Comment