Difference Between HashSet LinkedHashSet and TreeSet

HashSet, LinkedHashSet and TreeSet are all implementations of the Set interface.In this post lets see Difference Between HashSet LinkedHashSet and TreeSet.

1. Implementation

All these 3 implement the Set interface.
HashSet is backed by a hash table (actually a HashMap instance).
LinkedHashSet uses Hash table and linked list. It maintains a doubly-linked list running through all of its entries, thus maintaining the order of insertion.
TreeSet is a NavigableSet implementation based on a TreeMap.

2. Ordering

HashSet does not guarantee any order in which the elements are stored.
LinkedHashSet maintains the order in which the elements are inserted.
TreeSet sorts the elements in its natural ordering and ascending. You can provide a comparator to sort the elements stored in the TreeMap

3. Null values as Entries

HashSet and LinkedHashSet both allow Null elements to be added.
Null is not allowed in a TreeSet unless you specify a comparator that can handle a Null.

4. Performance

HashSet are the fastest in terms of basic opertaions like add, remove or search elements.
LinkedHashSet can be a little slower as they maintain a linked list which causes some performance overhead. But we never saw a major performance difference between HashSet and LinkedHashSet.
TreeSet are the slowest in comparision with the other two, due to the sorting done.

Lets see an example of performance when we add a lot of elements to all these Sets.


5. When to use

Since HashSet is the fastest, for any regular operations you should use HashSet. If you need to have a maintain the insertion order of elements use LinkedHashSet. If you want sorted set, then use TreeSet but at cost of performance.