Tuesday, 10 November 2015

TreeMap in Java

TreeMap is also one of the implementation of the Map interface like HashMap and LinkedHashMap. TreeMap class implements the NavigableMap interface and extends the AbstractMap class.

How it differs from other implementations of the Map interface like HashMap and LinkedHashMap is that objects in TreeMap are stored in sorted order. The elements are ordered using their natural 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

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.

Example code using TreeMap

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 TreeMap sorts the elements using their natural ordering 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 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)

TreeMap is not synchronized

TreeMap 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 this class' iterator method 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.

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 using different order then you need to provide your own comparator at map creation time. Let's see an example where we sort the Strings in descending order.

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 comparator is provided which reverses the sorting order. That comparator is provided at the map creation time in a constructor.

Points to remember

  1. TreeMap is one of the implementation of the Map interface.
  2. TreeMap stores its elements in sorted order. By default elements are sorted using their natural ordering.
  3. TreeMap doesn’t allow null as key though other Map implementation like HashMap and LinkedHashMap do allow one key as null.
  4. If you want to sort in any other order then you will have to provide comparator.
  5. TreeMap is not thread-safe.

That's all for this topic TreeMap in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

Source: http://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html


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

You may also like -

No comments:

Post a Comment