Wednesday, September 27, 2023

Difference between HashSet vs TreeSet in Java? [Answer]

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 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 the Comparator interface, by default TreeSet uses elements of natural order for sorting, which is defined by the compareTo() method of java.lang.Comparable interface.  What is the difference between HashSet and TreeSet is also one of the frequently asked Java interview questions, So you should know about similarities and differences between them? 

It also helps you to understand when to use both TreeSet and HashSet and what is the scenario when we should use these sets. Let's go through the similarities and differences between HashSet and TreeSet in Java.



Similarities between TreeSet and HashSet in Java

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

1. Set Interface
Both HashSet and TreeSet implement the Set interface.

2. Insertion Order
Both classes don't maintain the insertion order of elements.

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

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

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

6. 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.




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.


1. 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.


2. Ordering

HashSet is unordered when we store objects in HashSet it stores them in random order, which 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 is defined by supplied Comparator, and if you don't give any Comparator for TreeSet objects then it will use the natural ordering of elements e.g. Integers in their numeric order or String in their alphabetical order.


3. Null Value

HashSet allows a 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.


4. 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.


5. Speed and Performance

HashSet is faster than TreeSet for all general purposes. The add, remove and contains methods have 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.


6. Functionality

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

That's all about difference between HashSet and TreeSet in Java. So the conclusion here is which class we should use is totally depends on 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 a Red-Black tree data structure underneath to sort out the elements. 

When one needs to perform read/write operations frequently, then TreeSet is not a good choice.


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 drivers 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 a fail-fast and a fail-safe Iterator in Java? [answer]
So that's it about HashSet and TreeSet in Java. If you have any questions please ask in comments. If you have any feedback like whether you like this article or something can be improved upon, feel free to let me know in comments. Your Feedback means a lot to me. 

1 comment:

  1. In hashset heterogenous s are allowed where as in treeset heterogenous objects are not allowed..

    ReplyDelete

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