• ← Previous
• Next →

A SortedMap interface is one of the widely used Collection interfaces. We are going to discuss one of the implementation class of the SortedMap: TreeMap. As shown in the below figure, TreeMap is the implementation class of the SortedMap interface and also of NavigableMap, which extends SortedMap. We highly recommend that one should go through SortedMap Interface and NavigableMap Interface. before getting into the details of the TreeMap class.

Figure: Map Interfaces and Classes

The TreeMap class implements all the methods defined in SortedMap and NavigableMap interfaces. It does not provide any additional methods of its own! A TreeMap uses a Red-Black Tree as its underlying data structure. A Red-Black Tree is a very popular data structure, where operations like add, remove, find etc can be done in log(N) time.

A TreeMap inherits all the basic/fundamental properties of a Map and a SortedMap. And as we know, each key in the Map object (or SortedMap object, for that matter), can at most relate/map/correspond to one single value. In other words, A Map or a SortedMap cannot contain duplicate keys. And since a TreeMap inherits behavior of Map and SortedMap, even it cannot have duplicate keys.

Furthermore, all keys of a TreeMap are ordered using their natural ordering. Because all the keys of a TreeMap would be in a particular order, the elements should be comparable; a TreeMap cannot contain any keys that cannot be comparable. Thus, if we have two keys (let us say, key1 and key2), then key1.compareTo(key2) or comparator.compare(key1, key2) must not throw "ClassCastException".

To get more information about the natural ordering, please go through the Comparable and Comparator interfaces. The ordering of the keys can be noticed when iterating over a TreeMap.

TreeMap Class Constructors

TreeMap class provides four different types of Constructors to instantiate a TreeMap object. We list them in the table below.

With that, let us see an example that demonstrates the usage of the above constructors.

 import java.util.Comparator;
 import java.util.HashMap;
 import java.util.Map;
 import java.util.TreeMap;

 class ComparatorClassDemo implements Comparator {
     @Override
     public int compare(Object arg0, Object arg1) {
         Integer x = (Integer) arg0;
         Integer y = (Integer) arg1;
         if (x < y)
             return 1;
         else if (x > y)
             return -1;
         else
             return 0;
     }
 }

 public class TreeMapDemo {
     public static void main(String[] args) {
     	Map mobj = new HashMap();
 	mobj.put(1237,"John");
 	mobj.put(2013,"Ray");
 	mobj.put(1024,"Mike");

 	TreeMap tmObj1 = new TreeMap();
 	TreeMap tmObj2 = new TreeMap(new ComparatorClassDemo());
 	TreeMap tmObj3 = new TreeMap(mobj);

 	tmObj1.put(237,"Jay");
 	tmObj1.put(101,"Tom");
 	tmObj1.put(880,"Ryan");

 	tmObj2.put(237,"Jay");
 	tmObj2.put(101,"Tom");
 	tmObj2.put(880,"Ryan");

         System.out.println (" TreeMap1: " + tmObj1);
         System.out.println (" TreeMap2: " + tmObj2);
         System.out.println (" TreeMap3: " + tmObj3);
         System.out.println(" Comparator Object: " + tmObj2.comparator()
                            + ", Default Object (Comparable): " 
                            + tmObj1.comparator());
     }
 }

If you notice the object the above example, the keys of the "tmpObj2" TreeMap is sorted using a Comparator. A comparator object of class "ComparatorClassDemo" is passed as an argument, hence all the elements of TreeMap represented by the object "tmObj2" are sorted in descending order (the logic defined by the comparator) and NOT by the Natural order. The "ComparatorClassDemo" class implemented a Comparator and hence overrides the method "compare", hence all the keys that are inserted into the tmObj2 are compared using "compare()" method as opposed to the default "compareTo()" method defined by the Comparable Interface..

Let us Compile/run the program.

We provide the output below. If you notice, all the Keys of the Map are in sorted order. This free-of-cost sorting is the basic difference between a Map vs TreeMap. The first TreeMap presented by the object "tmObj1" is created by the default constructor and it sorts the elements using the Natural Ordering (Ascending order is the default natural order). On the other hand, the third TreeMap represented by "tmobj3 is created from the Map object passed to the Constructor.

  TreeMap1: {101=Tom, 237=Jay, 880=Ryan}
  TreeMap2: {880=Ryan, 237=Jay, 101=Tom}
  TreeMap3: {1024=Mike, 1237=John, 2013=Ray}
  Comparator Object: ComparatorClassDemo@1db9742, Default Object (Comparable): null

Clone Operation on the TreeMap

TreeMap interface provides an other important operation called "clone", where one can get to make a shallow copy of the TreeMap. What is a shallow copy? You might ask. Well, shallow-copy means that the elements of the TreeMap are not copied; instead, it just creates an instance of the TreeMap. And a change made using one object gets reflected in the other object as well. Basically, if you are familiar with "C" programming it like having two pointers to the same variable -- changes made by one pointer would be visible to the other pointer as well since they are both pointing to the same address!

An example program demonstrating the concept of "Clone" method is available in ArrayList Class. The concept of "Clone" is same, be it an ArrayList or HashSet or a TreeMap.

• ← Previous
• Next →