Tuesday, 13 October 2015

TreeSet in Java

TreeSet is also one of the implementation of the Set interface like HashSet and LinkedHashSet. TreeSet class implements the NavigableSet interface and extends the AbstractSet class.

Just like other implementations of the Set interface HashSet and LinkedHashSet, TreeSet also stores unique elements. How TreeSet differs from other implementations is that objects in TreeSet are stored in sorted order. The elements are ordered using their natural ordering or a comparator can be provided at set creation time to provide custom ordering (We'll see an example a little later).

How TreeSet is implemented

TreeSet uses a tree data structure to store its elements thus providing guaranteed log(n) time cost for the basic operations (add, remove and contains).

As we have seen while discussing HashSet and LinkedHashSet internally these implementations use their map counterparts i.e. HashMap and LinkedHashMap respectively. Same with TreeSet it also uses TreeMap internally to store its elements.

Example code using TreeSet

public class TreeSetDemo {

    public static void main(String[] args) {
        Set<String> citySet = new TreeSet<String>();
        
        citySet.add("Delhi");
        citySet.add("Mumbai");
        citySet.add("Bangalore");
        citySet.add("Delhi");
        citySet.add("Chennai");
        citySet.add("Hyderabad");
        
        // Iterating the Set
        for(String str : citySet){
            System.out.println("City Name - " + str);
        }
        
        Set<Integer> numberSet = new TreeSet<Integer>();
        numberSet.add(6);
        numberSet.add(76);
        numberSet.add(1);
        numberSet.add(45);
        numberSet.add(89);
        numberSet.add(8);
        
        // Iterating the Set
        for(Integer num : numberSet){
            System.out.println("Number - " + num);
        }
    }
}

Output

City Name - Bangalore
City Name - Chennai
City Name - Delhi
City Name - Hyderabad
City Name - Mumbai
Number - 1
Number - 6
Number - 8
Number - 45
Number - 76
Number - 89

Here I have created 2 TreeSets, one stores Strings and another Integers. It can be seen that the TreeSet sorts the elements using their natural ordering which is ascending for both String and Integer. Also note that though Delhi is added twice but it is stored only once, so uniqueness is maintained.

Tree Set doesn't allow null

Though HashSet and LinkedHashSet allow one null, TreeSet doesn't allow null as element. Any attempt to add null in a TreeSet will result in a NullPointerException.

public class TreeSetDemo {

    public static void main(String[] args) {
        Set<String> citySet = new TreeSet<String>();
        
        citySet.add("Delhi");
        citySet.add("Mumbai");
        citySet.add(null);
        citySet.add("Delhi");
        citySet.add("Chennai");
        citySet.add("Hyderabad");
        
        // Iterating the Set
        for(String str : citySet){
            System.out.println("City Name - " + str);
        }
    }
}

Output

Exception in thread "main" java.lang.NullPointerException
 at java.util.TreeMap.put(Unknown Source)
 at java.util.TreeSet.add(Unknown Source)
 at org.netjs.prog.TreeSetDemo.main(TreeSetDemo.java:14)

Sorting elements in different order in TreeSet

As already mentioned by default elements are stored in TreeSet using natural ordering. If you want to sort using different order then you need to provide your own comparator at set creation time. Let's see an example where we sort the Strings in descending order.

public class TreeSetDemo {

    public static void main(String[] args) {
        // Providing custom compartor
        Set<String> citySet = new TreeSet<String>(new CityComparator());
        
        citySet.add("Delhi");
        citySet.add("Mumbai");
        citySet.add("Bangalore");
        citySet.add("Chennai");
        citySet.add("Hyderabad");
        
        // Iterating the Set
        for(String str : citySet){
            System.out.println("City Name - " + str);
        }
    }

}

// Comparator class
class CityComparator implements Comparator<String>{
    @Override
    public int compare(String str1, String str2) {
        return str2.compareTo(str1);
    }    
}

Output

City Name - Mumbai
City Name - Hyderabad
City Name - Delhi
City Name - Chennai
City Name - Bangalore

Here note that a comparator is provided which reverses the sorting order. That comparator is provided at the set creation time in a constructor.

TreeSet is not synchronized

TreeSet is not thread safe. In case we need to Synchronize it, it should be synchronized externally. That can be done using the Collections.synchronizedSet method.

Set s = Collections.synchronizedSet(new LinkedHashSet(...));

TreeSet class's iterator is fail-fast

The iterators returned by this class's iterator method are fail-fast, if the set is 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.

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


Related Topics

  1. How HashSet works internally in Java
  2. LinkedHashSet in Java
  3. How ArrayList works internally in Java
  4. How HashMap internally works in Java
  5. Java Collections interview questions

You may also like -

No comments:

Post a Comment