HashSet vs TreeSet in Java? Similarities and Differences

HashSet and TreeSet both implement same interface i.e  java.util.Set interface and they possess the quality of Set interface means duplicate elements are not allowed. Both HashSet and TreeSet are used for to store unique elements, but HashSet doesn't care about any order and TreeSet keeps a thing in order. Ordering or sorting on TreeSet can be customized by using Comparator interface, by default TreeSet uses elements natural order for sorting, which is defined by compareTo() method of java.lang.Comparable interface. What is the difference between HashSet and TreeSet is is also one the frequently asked Java interview question, So you should know about similarities and difference between them? It also helps you to understand when to use both TreeSet and HashSet and what are the scenario when we should use this sets. Let's go through the similarities and difference between HashSet and TreeSet in Java.

Similarities between TreeSet and HashSet

Here are some similarities between these two implementations of java.util.Set interface from Collection framework.

Set Interface
Both HashSet and TreeSet implements Set interface.

Insertion Order
Both class don't maintain insertion order of elements .

Duplicate value
Both classes don't allow duplicate elements, add() method reject them by returning false.

Both classes are not shared between multiple threads and not synchronized.

Iterator of both TreeSet and HashSet are failed fast.They will throw ConcurrentModificationException if  the Set is modified once the iteration begins.

Cloneable and Serializable
Both classes implement Cloneable and Serializable interface, which means you can serialize a TreeSet and HashSet and save int into the disk or send over the network to other JVM.

You can also check Java Programming Interview Exposed by Markham for more of such questions from Java developer interviews. One of a complete book for getting prepared for Java JEE interviews.

Difference between TreeSet and HashSet in Java

Difference between HashSet and TreeSet in Java

Now let's see some differences between these two classes, this will help you to decide when to use TreeSet and HashSet class in Java.

Internal Structure
HashSet internally uses HashMap to store its element, while TreeSet uses TreeMap to store its element internally. See this article to learn more about how HashSet works in Java.

HashSet is unordered when we store objects in HashSet it stores then in random order, means if we want to print the element by using its Iterator, their order does not guarantee that the first element we inserted will be printed first.

But in the case of TreeSet, the order of elements are defined by supplied Comparator, and if you don't give any Comparator for TreeSet objects  then it will use natural ordering of elements e.g. Integers in their numeric order or String in their alphabetic order.

Null Value
HashSet allows maximum  of one null element, which means you can store only one null value inside HashSet. But TreeSet won't allow any null object and you will get NullPointerException if you try to store null values in TreeSet. Why? because TreeSet sorts element as soon as you add it into TreeSet, if the object is null then calling compareTo() on that will throw NullPointerException.

Comparison method
HashSet uses equal() and hashcode() methods to compare the elements, while TreeSet we can implements compareTo() method of Comparator interface so we have compare() and compareTo() method ,TreeSet  does not use equal() and  hashcode() method.

Speed and Performance
HashSet is faster than TreeSet for all general purpose .The add, remove and contains methods has constant time complexity O(1)  for HashSet, which means HashSet offers constant time cost for adding, removing and checking if an object exists in Set.

TreeSet performance is less as compared to HashSet as TreeSet has to sort the element after each insertion and removal Operation. TreeSet offers log(n) time cost for dd, remove, and contains  operations.

TreeSet offers sorting which is not provided by HashSet. HashSet also has less methods as compared to TreeSet. TreeSet is rich in functionality as compare to HashSet. Functions like pollFirst(), pollLast(), first(), last(), ceiling(), lower() etc makes TreeSet rich in functionality wise.

Difference between HashSet and TreeSet in Java

So the conclusion here is which class we should use is totally depends on upon our nee. If we want to sort the element according to our need use Comparator and this is possible in TreeSet only but  if we are looking for fast and better performance we should go for HashSet and also if we don't want to maintain order. TreeSet uses Red- Black tree algorithm underneath to sort out the elements. When one need to perform read/write operations frequently, then TreeSet is not a good choice.

So that's it about HashSet and TreeSet in Java.

Other interview questions based upon differences of two classes in Java :
  • What is the difference between Comparator and Comparable in Java? [answer]
  • The difference between type 1, 2, 3 and 4 JDBC driver in Java? [answer]
  • The difference between CopyOnWriteArrayList and Synchronized ArrayList in Java? [answer]
  • What is the difference between Abstraction and Polymorphism in Java? [answer]
  • What is the difference between fail-fast and fail-safe iterator in Java? [answer]

No comments:

Post a Comment