Java: Hashset Vs TreeSet - when should I use over the other?
JavaCollectionsJava Problem Overview
All I have been reading lots of blogs on this subject but still I could not get clear idea when to use one over another hashset or tree set.
Taken an example:
-
I have a comparable objects. I have put them in HashSet. Now when (only when I want) i want to set to be sorted based on compareTo logic, I can call Collections.sort(object)
-
whereas Treeset by default always use the compareTo or compare(obj1, obj2) all the time. Hence performance will be hit with TreeSet but output will be same as #1 (Collections.sort).
Is this understanding correct?
Java Solutions
Solution 1 - Java
HashSet is Implemented using a hash table. Elements are not ordered. The add, remove,
and contains methods have constant time complexity O(1).
TreeSet is implemented using a tree structure(red-black tree in algorithm book). The elements in a set are sorted, but the add, remove, and contains methods has time complexity O(log (n)). It offers several methods to deal with the ordered set like first(), last(), headSet(), tailSet()
, etc.
-
First major difference between
HashSet
andTreeSet
is performance.HashSet
is faster thanTreeSet
and should be preferred choice if sorting of element is not required. -
Second difference between
HashSet
andTreeSet
is thatHashSet
allows null object butTreeSet
doesn't allow null Object and throwNullPointerException
, Why, becauseTreeSet
usescompareTo()
method to compare keys andcompareTo()
will throwjava.lang.NullPointerException
. -
Another significant difference between
HashSet
andTreeSet
is that ,HashSet
is backed byHashMap
whileTreeSet
is backed by NavigableMap in Java. -
One more difference between
HashSet
andTreeSet
which is worth remembering is that HashSet usesequals()
method to compare two object in Set and for detecting duplicates whileTreeSet
usescompareTo()
method for same purpose. ifequals()
andcompareTo()
are not consistent, i.e. for two equal object equals should return true whilecompareTo()
should return zero, than it will break contract of Set interface and will allow duplicates in Set implementations like TreeSet -
Now most important difference between
HashSet
andTreeSet
is ordering.HashSet
doesn't guaranteed any order whileTreeSet
maintains objects in Sorted order defined by eitherComparable
orComparator
method in Java. -
TreeSet
does not allow to insertHeterogeneous
objects. It will throwclassCastException
atRuntime
if trying to add hetrogeneous objects, whereasHashSet
allows hetrogeneous objects.