June 30, 2022

HashSet Vs LinkedHashSet Vs TreeSet in Java

If you have to store only unique elements i.e no duplicates in your Java application you’d probably choose to use one of the Set implementation in Java; HashSet, TreeSet or LinkedHashSet. Though all these Set implementations store unique elements but they do differ on the points like ordering of elements, performance they offer, null value permitted or not. In this post we’ll see the differences among HashSet, LinkedHashSet and TreeSet in Java which will help you to decide which Set implementation serves your purpose in a better way.

HashSet Vs LinkedHashSet Vs TreeSet in Java

1- Ordering of the Element-

HashSet- HashSet is an unordered collection. Element is stored based on the hash value calculated for the element.

LinkedHashSet- In LinkedHashSet insertion order of the elements is maintained.

TreeSet- TreeSet stores its element in sorted order. By default elements are sorted in natural ordering but you can provide a Comparator if you want different ordering.

2- Internal implementation-

HashSet- Internally HashSet uses a HashMap to store is element.

LinkedHashSet- Internally LinkedHashSet is backed by a LinkedHashMap instance.

TreeSet- Internally TreeSet uses a TreeMap to store its elements.

3- Permitting null value-

HashSet- HashSet allows one null value.

LinkedHashSet- LinkedHashSet allows one null value.

TreeSet- In TreeSet null is not permitted. NullPointerException is thrown if you try to add null to a TreeSet.

4- Element comparison-

HashSet- In order to compare elements so that no duplicate elements are added HashSet uses equals() and hashCode() methods.

LinkedHashSet- LinkedHashSet also uses equals() and hashCode() methods.

TreeSet- TreeSet instance performs all element comparisons using its compareTo (or compare) method.

5- Performance-

HashSet- HashSet is the fastest among the three as it doesn’t have the added functionality of maintaining insertion order or sorting. HashSet offers constant time performance O(1) for the basic operations like add, remove, contains and size assuming the hash function disperses the elements properly among the buckets. If HashCode is not proper and the elements are not dispersed properly then the performance may degrade to O(n) in worst case.

LinkedHashSet- Performance of LinkedHashSet is just slightly below that of HashSet. It is because of the fact that LinkedHashSet maintains a doubly linked list running through all of its entries. This linked list defines the iteration ordering.

TreeSet- TreeSet is slow as it has to keep its element sorted. It uses a tree based structure for the same and because of that TreeSet provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

That's all for the topic HashSet Vs LinkedHashSet Vs TreeSet in Java. If something is missing or you have something to share about the topic please write a comment.


You may also like

No comments:

Post a Comment