---
description: Java Collections Interview Question
---

# Sep 2, 2018

## Difference Between HashSet And TreeSet

**1. Ordering :** `HashSet` stores the object in random order. There is no guarantee that the element we inserted first in the `HashSet` will be printed first in the output.&#x20;

For example

```java
import java.util.HashSet;

public class HashSetExample {
    
    public static void main(String[] args) {
        
        HashSet<String>  obj1 = new HashSet<String>();
        obj1.add("Alive");
        obj1.add("is");
        obj1.add("Awesome");
        System.out.println(obj1);        
    }    
} 
 
// OUTPUT : [is, Awesome, Alive]   
```

Elements are sorted according to the natural ordering of its elements in TreeSet. If the objects can not be sorted in natural order than use [compareTo() method to sort the elements](http://javahungry.blogspot.com/2013/08/difference-between-comparable-and.html) of `TreeSet` object.

```java
import java.util.TreeSet;

public class TreeSetExample {
    
    public static void main(String[] args) {
        
        TreeSet<String>  obj1= new TreeSet<String>();
        obj1.add("Alive");
        obj1.add("is");
        obj1.add("Awesome");
        System.out.println(obj1);
        
    }
    
}

// OUTPUT : [Alive, Awesome, is]   
```

**2. Null value :**   **HashSet can store `null` object while TreeSet does not allow `null` object**. If one try to store null object in TreeSet object , it will throw `Null Pointer Exception`.\
\
**3. Performance :** `HashSet` take **constant** time performance for the basic operations like add, remove contains and size. While `TreeSet` guarantees **`log(n)`** time cost for the basic operations (add, remove, contains).\
\
**4. Speed :** **HashSet is much faster than TreeSet**, as performance time of HashSet is constant against the log time of TreeSet for most operations (add, remove, contains and size) . Iteration performance of HashSet mainly depends on the load factor and initial capacity parameters. \
\
**5. Internal implementation :**  As we have already discussed [How hashset internally works in java ](http://javahungry.blogspot.com/2013/08/how-sets-are-implemented-internally-in.html)thus, in one line HashSet are internally backed by HashMap. While TreeSet is backed by a Navigable TreeMap.&#x20;

**6. Functionality :**    TreeSet is rich in functionality as compare to HashSet. Functions like pollFirst(), pollLast(), first(), last(), ceiling(), lower() etc. makes TreeSet easier to use than HashSet. \
\
**7. Comparision :** HashSet uses equals() method for comparison in java while TreeSet uses compareTo() method for maintaining ordering .

**To whom priority is given TreeSet comparator or Comparable.compareTo() .**\
\
Suppose there are elements in TreeSet which can be naturally sorted by the TreeSet , but we also added our own sorting method by implementing Comparable interface compareTo() method .\
Then to whom priority is given.\
\
Answer to the above question is that the Comparator passed into the TreeSet constructor has been given priority.\
According to [Oracle Java docs](http://docs.oracle.com/javase/6/docs/api/java/util/TreeSet.html#TreeSet%28java.util.Comparator%29) \
\
`public TreeSet(Comparator comparator)`\
\
Constructs a new, empty tree set, sorted according to the specified comparator.\
\
Parameters:\
&#x20;  \
comparator - the comparator that will be used to order this set. If null, the natural ordering of the elements will be used.\
\
**Similarities Between HashSet and TreeSet**\
\
**1. Unique Elements :**   Since HashSet and TreeSet both implements Set interface . Both are allowed to store only unique elements in their objects. Thus there can never be any duplicate elements inside the HashSet and TreeSet objects.\
\
**2.** **Not Thread Safe :** HashSet and TreeSet both are not synchronized or not thread safe.HashSet and TreeSet, both implementations are not synchronized. If multiple threads access a hash set/ tree set concurrently, and at least one of the threads modifies the set, it must be synchronized externally.\
\
**3. Clone() method copy technique:**  Both HashSet and TreeSet uses shallow copy technique to create a clone of  their objects .\
\
**4. Fail-fast Iterators :**  The iterators returned by this class's  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.  Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at   an undetermined time in the future.\
\
**When to prefer TreeSet over HashSet**\
\
**1.  Sorted unique elements are required instead of unique elements.The sorted list given by TreeSet is always in ascending order.**\
\
**2.   TreeSet has greater locality than HashSet.**\
\
If two entries  are near by in the order , then TreeSet places them near each other in data structure and hence in memory, while HashSet spreads the entries all over memory  regardless of the keys they are associated to. \
&#x20;    \
As we know Data reads from the hard drive takes much more latency time than data read from the cache or memory. In case data needs to be read from hard drive than prefer TreeSet as it has greater locality than HashSet.\
\
3\. TreeSet uses Red- Black tree algorithm underneath to sort out the elements. When one need to perform read/write operations frequently , then TreeSet is a good choice.



## References

{% embed url="http://javahungry.blogspot.com/2014/03/difference-between-hashset-and-treeset-similarities-and-example.html" %}

{% embed url="http://javahungry.blogspot.com/2013/12/difference-between-arraylist-and-vector-in-java-collection-interview-question.html" %}

{% embed url="http://javahungry.blogspot.com/2013/08/difference-between-comparable-and.html" %}

