Tuesday, 17 November 2015

HashSet Vs LinkedHashSet Vs TreeSet in Java

Though HashSet, LinkedHashSet and TreeSet all are implementation of the Set interface and share some traits like storing only the unique elements, not being thread-safe but there are certain differences too related to performance, how elements are ordered etc. So it is very important to know these differences as it will help you to make an informed choice which Set implementation to use to meet the requirement.

Differences among HashSet, LinkedHashSet and TreeSet

  1. First and most important difference is related to Ordering of the elements.
    HashSet is unordered, it will store elements on the basis of the calculated hash that's it.
    LinkedHashSet maintains the insertion order of the elements.
    TreeSet keeps the element in sorted order. The sorting order TreeSet follows by default is known as the natural ordering of the elements.
  2. Another difference is related to allowing null value.
    HashSet as well as LinkedHashSet allow null value to be stored. Mind you only one null value is allowed in both HashSet and LinkedHashSet.
    TreeSet does not allow null value, trying to add null to a TreeSet will result in a null pointer exception.
  3. For HashSet and LinkedHashSet comparison of the elements is done using equals() method. Note that set allows only unique elements, and that uniqueness is maintained by using the equals() method to compare elements.
    TreeSet does the comparison of the element using the compareTo (or compare) method, depending on whether sorting is done using Comparable or Comparator.
  4. Performance wise HashSet is at the top as it has no added baggage of insertion ordering or sorting. If hashing is done correctly HashSet offers constant time performance O(1) for the basic operations (add, remove, contains and size). As I mentioned this performance is assuming that the hash function disperses the elements properly among the buckets. If HashCode is not proper the performance may degrade and in worst case it will be O(n).
    For LinkedHashSet performance is likely to be just slightly below that of HashSet, due to the added expense of maintaining the linked list.
    TreeSet has to sort elements with every insertion so that way performance is slow, but TreeSet provides guaranteed log(n) time cost for the basic operations (add, remove and contains) irrespective of the number of elements stored.

That's all for this topic HashSet Vs LinkedHashSet Vs TreeSet in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. How HashSet works internally in Java
  2. TreeSet in Java
  3. EnumSet in Java
  4. How HashMap internally works in Java
  5. How ArrayList works internally in Java
  6. Difference between HashMap and HashTable in Java

You may also like -

1 comment:

  1. Very Good Explanation...thanks a lot for providing such a good site...

    ReplyDelete