6 Difference between LinkedHashSet vs TreeSet vs HashSet in Java

LinkedHashSet, TreeSet, and HashSet are three of most popular implementation of Set interface in Java Collection Framework. Since they implement Set interface, they follow its contracts for not allowing duplicates. All these implementation except, TreeSet uses equals() method to check for duplicates, on the other hand TreeSet use compareTo() or compare() method for comparing objects and can break Set interface contract of unique element, if equals method is not consistent with compareTo() or compare() method. In this Java Collection tutorial, we will see the difference between LinkedHashSet vs TreeSet vs HashSet on different points e.g. speed, performance, ordering, synchronization etc. Based upon these differences we can also decide when to use LinkedHashSet vs TreeSet vs HashSet in Java.

TL;DR, Use HashSet for all general purpose usage i.e. where you need to store only unique elements without any ordering requirement. If you need to maintain order in which elements are added into Set then use LinkedHashSet, it provides ordering with little impact on performance. Use TreeSet when you absolutely nee to keep elements in specifically sorted order e.g. keeping employees in increasing order of their age or salary.

Remember, TreeSet is significantly slower than LinkedHashSet and HashSet because of this sorting overhead. BTW, if you are preparing for Java interviews, I suggest taking a look at Java Programming Interview Exposed by Markham. You will find a lot of such question with a very detailed answer.

Difference between LinkedHashSet vs TreeSet vs HashSet

Before comparing them, let's see some similarity between them. All of them implement Set and Collection interface, so they can be passed to a method which accepts Set as an argument. Though they all are set, they differ in their implementation e.g. LinkedHashSet is backed by linked list and HashMap, TreeSet is implemented as TreeMap till Java 5 and now using NavigableMap from Java 6 onward, and HashSet is also backed by HashMap in Java. Now let's see some comparison between them :

1) Synchronization
All three i.e. HashSet, TreeSet, and LinkedHashSet are not synchronized. They can not be shared between multiple threads until specifically synchronized. It's easy to create synchronized Set, though, all you need to do is use java.util.Collections utility class as shown below :

Synchronizing HashSet in Java

Set s = Collections.synchronizedSet(new HashSet(...));

Synchronizing LinkedHashSet in Java

Set s = Collections.synchronizedSet(new LinkedHashSet(...));

Synchronizing TreeSet in Java

Set s = Collections.synchronizedSet(new TreeSet(...));

2) Ordering
HashSet doesn't guarantee any order, while TreeSet sorts all object based upon there natural ordering by using compareTo() method, or custom order by using compare() method Comparator passed to them. LinkedHashSet also provides ordering support to keep elements in the order they are added into Collection. Actually, this property is also derived from the fact that they are backed by respective Map implementation. See the difference between HashSet and HashMap for few more details on these two classes.

3) Null Element
This property can be deduced form HashMap, LinkedHashMap, and TreeMap since HashSet internally uses HashMap, LinkedHashSet internally uses LinkedHashMap and TreeSet internally uses TreeMap. Both HashMap and LinkedHashMap allows one null key and so are these two Set implementations. On the other hand, since TreeMap doesn't allow null keys, TreeSet doesn't allow null elements and throws java.lang.NullPointerException when you try to add a null object. The main reason of this is the use of compareTo() and compare() method, which throws NullPointerException if one element is null, but it truly depends on implementation.

4) Implementation
HashSet internally uses a HashMap with dummy value object, while LinkedHashSet uses a LinkedHashMap to guarantee insertion order. When you iterate through HashSet order is unpredictable but when you iterate through LinkedHashSet, you iterate elements in the order they are added. TreeSet is backed by a navigable Map, as shown below :

Source code of HashSet

 public HashSet(int initialCapacity) {
   map = new HashMap<E,Object>(initialCapacity);

Source code of LinkedHashSet

 * Constructs a new, empty linked hash set.  (This package private constructor
 * is only used by LinkedHashSet.) The backing HashMap instance is a 
 * LinkedHashMap with the specified initial capacity and the specified load 
 * factor
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);

Source code of  TreeSet

public TreeSet() {
        this(new TreeMap<E,Object>());

Earlier TreeSet is internally implemented TreeMap but with introduction of NavigableMap in Java 1.6, its implementation has changed.

5) Iterator
Iterator retuned by all three Set implementations are fail-fast, which means if you modify collection once iteration begins i.e. add or delete elements without using Iterator's remove method, it will throw ConcurrentModificationException. Also Iterator of HashSet doesn't guarantee any order, while Iterator of LinkedHashSet let you iterate in the order elements are added. You can also see this article to learn more about different types of Iterator in Java.

6) Performance
Out of HashSet, LinkedHashSet and TreeSet,  HashSet is fastest for common operation e.g. add, search and remove, LinkedHashSet is close second, as it suffers a little drop in performance due to overhead of maintaining doubly linked list when an element is inserted or deleted. TreeSet is much slower than these two because it needs to perform sorting every time there is change in TreeSet. It means by default you should use HashSet, until and unless you really need LinkedHashSet or TreeSet. You can also check this article for more difference between TreeSet and TreeMap in Java.


Here is a nice table to compare different implementation of Set interface e.g. EnumSet, TreeSet, CopyOnWriteArraySet, HashSet, LinkedHashSet and ConcurrentSkipListSet on different parameters e.g. data structure, sorting, iterator and how they handle null input.
Difference between LinkedHashSet, TreeSet and HashSet in Java

That's all about difference between LinkedHashSet vs TreeSet vs HashSet in Java. You should use HashSet for general purpose Set requirement, where you need to store only unique elements without any sorting or ordering requirement, if you need to maintain the order on which elements are added into Set, apart from guarantee of unique elements, use LinkedHashSet. If you need to keep your elements in a particular sorting order use TreeSet, you can either keep elements in their natural order or you can customize their sorting order by providing a Comparator e.g. keeping notes in increasing order of their value.

Further Reading
  • Java Programming Interview Exposed by Makham (see here)
  • Java Generics and Collection by Maurice Naftalin (see here)

Wish you all very Happy New Year 2014

1 comment: