Difference between HashSet and TreeSet in Java

Difference between HashSet and TreeSet in Java
There are several differences between a HashSet and a TreeSet are similar to what we discussed as a difference between TreeMap and HashMap. Anyway, Set and Map are two completely different interfaces so we will revisit those differences here. Probably the most important difference between HashSet and TreeSet is the performance. HashSet is faster than TreeSet which means if you need performance use HashSet but HashSet doesn't provide any kind of ordering so if you need ordering then you need to switch to TreeSet which provides sorting of keys

Sorting can be natural order defined by a Comparable interface or any particular order defined by a Comparator interface in Java.

Apart from the differences between HashSet and TreeSet, there are some common things between them. let's see what is common between HashSet and TreeSet in Java.

 By the way, this is one of the popular Java collection interview questions much like ArrayList vs Vector and Hashtable vs HashMap. If you are going for any Java programming interview, it's worth preparing.



What is Common in HashSet and TreeSet in Java

As I said there are a lot of things that are common between HashSet and TreeSet in Java, let’s have a look:

1)Both HashSet and TreeSet implements java.util.Set interface which means they follow contract of Set interface and doesn't allow any duplicates.

2)Both HashSet and TreeSet are not thread-safe and not synchronized. Though you can make them synchronized by using the Collections.synchronizedSet() method.

3) The third similarity between TreeSet and HashSet is that Iterator of both classes is fail-fast in nature. They will throw ConcurrentModificationException if Iterator is modified once Iterator is created. this is not guaranteed and application code should not rely on this code but Java makes best effort to fail as soon as it detects a structural change in underlying Set.



HashSet vs TreeSet in Java

Now let's see a couple of differences between HashSet vs TreeSet in Java. This is enough to decide whether you should use HashSet or TreeSet in a given scenario.

1) The first major difference between HashSet and TreeSet is performance. HashSet is faster than TreeSet and should be the preferred choice if sorting of elements is not required. TreeSet is internally backed by a Red-Black tree. For a detailed description of the Red-Black Tree, you should read a good book on data structure and algorithms like Introduction to Algorithms by Thomas Corman.

The performance difference comes from the underlying data structure used by TreeSet and HashSet i.e. a tree and a hash table. Adding an element of a tree is slower than adding it to a hash table but it is still much faster than adding it into the right place in the linked list or array. 

If the tree contains n elements, then an average log2N comparisons are required to find the correct position for a new element. For example, if the tree contains 1000 elements then adding a new element requires about 10 comparisons.


2) Second difference between HashSet and TreeSet is that HashSet allows null object but TreeSet doesn't allow null Object and throw NullPointerException, Why, because TreeSet uses compareTo() method to compare keys and compareTo() will throw java.lang.NullPointerException as shown in below example :

HashSet<String> hashSet = new HashSet<String>();
hashSet.add("Java");
hashSet.add(null);
       
TreeSet<String> treeSet = new TreeSet<String>();
treeSet.add("C++");
treeSet.add(null); //Java.lang.NullPointerException
Output:
Exception in thread "main" java.lang.NullPointerException
        at java.util.TreeMap.put(TreeMap.java:541)
        at java.util.TreeSet.add(TreeSet.java:238)
        at test.CollectionTest.main(CollectionTest.java:27)
Java Result: 1


3) Another significant difference between HashSet and TreeSet is that HashSet is backed by HashMap while TreeSet is backed by TreeMap in Java.


4) One more difference between HashSet and TreeSet which is worth remembering is that HashSet uses equals() method to compare two objects in Set and for detecting duplicates while TreeSet uses the compareTo() method for the same purpose. 

If equals() and compareTo() are not consistent, i.e. for two equal object equals should return true while compareTo() should return zero then it will break the contract of Set interface and will allow duplicates in Set implementations like TreeSet


5) Now the most important difference between HashSet and TreeSet is ordering. HashSet doesn't guarantee any order while TreeSet maintains objects in the Sorted order defined by either Comparable or Comparator method in Java.

Here is a nice summary slide of key differences between TreeSet and HashSet in Java, which compares both of these collections on ordering, sorting, performance, underlying data structure, the method used for duplicate detection, and how they are implemented in JDK.



That's all on the difference between HashSet and TreeSet in Java. Use HashSet if you don't need sorting and looking for better performance while TreeSet is the first choice if you need to maintain objects in sorted order in Java. Both of them will not allow duplicates and maintain a unique set of elements. 

Other Java articles you may like 
how to traverse over ArrayList in Java 
How to sort ArrayList in ascending order in Java
How to convert ArrayList to HashSet in Java
Difference between List and Set in Java

Now, its your turn to answer a quiz, Can you store null object on HashSet and TreeSet in Java? 

10 comments:

  1. hi ..i think in Non empty TreeSet we can't add null values but empty Treeeset we can add null values once because Treeset doesn't allow Homogenous elements

    ReplyDelete
  2. No Dear...TreeSet doesn't allow null value.

    ReplyDelete
    Replies
    1. It allows but at runt ime it will through error.

      Delete
    2. No, I have actually coded it, it doesn't allow null value in any case.

      Delete
    3. It allows once if treeSet is empty.

      Delete
  3. Bhanu is right, if TreeSet is empty then we can add Null value but if it not empty then can not.

    ReplyDelete
  4. In empty treeset also null is not allowed. it throws null pointer exception

    ReplyDelete
  5. I tried to add null for empty tree set, it is throwing null pointer exception. Any why Treeset not allowing null.

    ReplyDelete
  6. Not allowing in any case, Treeset throwing Null pointer exception.

    ReplyDelete
  7. Treeset allows null, considering the values are coming as null runtime. However it throws an exception runtime.

    A new point to this article is :
    Treeset will sort the values based on the compareTo() method for the object we are storing in Treeset.
    Now think about storing Objects in Treeset without any implementation of comparator/comparable.
    Example:
    Add an Employee object to Treeset which is not implemented by comparator.
    Treeset allows the first object to add in.
    For second object it shows an compile time error.

    Its because first object it doesn't require any comparison as its first and only one object.

    Looks like it will check the comparisons from second entry in the set.

    Try adding only one null and no other entries. Now, print the values you should be able to see null in Treeset as per my understanding.

    Thanks
    Nagendar M

    ReplyDelete

Feel free to comment, ask questions if you have any doubt.