HashSet vs TreeSet

HashSet vs TreeSet


Three most used implementations of Set interface are HashSet, TreeSet and LinkedHashSet. For a novice, it looks difficult to understand. When a list of differences is presented all at a single place, it is easier to understand.

Start reading HashSet vs TreeSet

Programs are available at HashSet Tutorial and TreeSet Tutorial.

First let us see the similarities.

1. Being derived for Collection and Set interfaces, both can make use of the methods of these two interfaces.
2. Being derived from Set interface, both will not accept duplicate elements.
3. Methods of both are not synchronized and thereby not thread-safe for multithreaded environments. Synchronized versions can be obtained using Collections.synchronizedSet() method.
4. Both can use Iterator interface with fail-fast nature; when iterator is modified, it throws ConcurrentModificationException.

List of Difference between HashSet and TreeSet Java
Feature HashSet TreeSet
1. Performance on operational methods like add(), remove() and contains() Gives constant time performance, O(1) Gives log(n) time cost performance, O(log (n)). It’s performance is almost 1/3 higher than TreeSet, I observed.
2. Order of elements Does not return the elements in the same way added Returns the elements in ascending order or as per the Comparator supplied. Performance low due to added cost of sorting.
3. Tuning Parameters To optimize memory usage Initial capacity and load factor can be set No such parameters are available as tree is always balanced
4. More operative methods only add() and remove() methods exist Apart add and remove methods, also exist overloaded subSet(), headSet() and tailSet()
5. Internal implementation uses Hashtable Internal implementation uses tree structures (red-black tree algorithm)
6. Preference Due to higher performance, it should be preferred (when sorting is not much needed) Should be preferred only when sorting order is required
7. Null acceptance Accepts null object Does not accept null object (throws NullPointerException)
8. Detection of similar elements to avoid duplicates Uses equals() method Uses compareTo() method

One thought on “HashSet vs TreeSet

  1. Gaurav Pareek

    Can you please explain 1st point ( Performance on operational methods like add(), remove() and contains()) in difference between HashSet and TreeSet. I am confused!!

Leave a Reply

Your email address will not be published. Required fields are marked *