Difference between TreeSet, LinkedHashSet and HashSet in Java with Example

TreeSet, LinkedHashSet and HashSet all are implementation of Set interface and by virtue of that, they follows contract of Set interface i.e. they do not allow duplicate elements. Despite being from same type hierarchy,  there are lot of difference between them; which is important to understand, so that you can choose most appropriate Set implementation based upon your requirement. By the way difference between TreeSet and HashSet or LinkedHashSet is also one of the popular Java Collection interview question, not as popular as Hashtable vs HashMap or ArrayList vs Vector but still appears in various Java interviews. In this article we will see difference between HashSet, TreeSet and LinkedHashSet on various points e.g. Ordering of elements, performance, allowing null etc and then we will see When to use TreeSet or LinkedHashSet or simply HashSet in Java.

Difference between TreeSet, LinkedHashSet and HashSet in Java

TreeSet, LinkedHashSet and HashSet in Java are three Set implementation in collection framework and like many others they are also used to store objects. Main feature of TreeSet is sorting,  LinkedHashSet is insertion order and HashSet is just general purpose collection for storing object. HashSet is implemented using HashMap in Java while TreeSet is implemented using TreeMap.  TreeSet is a SortedSet implementation which allows it to keep elements in the sorted order defined by either Comparable or Comparator interface. Comparable is used for natural order sorting and Comparator for custom order sorting of objects, which can be provided while creating instance of TreeSet. Anyway before seeing difference between TreeSet, LinkedHashSet and HashSet, let's see some similarities between them:

1) Duplicates : All three implements Set interface means they are not allowed to store duplicates.

2) Thread safety : HashSet, TreeSet and LinkedHashSet are not thread-safe, if you use them in multi-threading environment where at least one Thread  modifies Set you need to externally synchronize them.

3) Fail-Fast Iterator : Iterator returned by TreeSet, LinkedHashSet and HashSet are fail-fast Iterator. i.e. If Iterator is modified after its creation by any way other than Iterators remove() method, it will throw ConcurrentModificationException with best of effort. read more about fail-fast vs fail-safe Iterator here

Now let’s see difference between HashSet, LinkedHashSet and TreeSet in Java :

Performance and Speed : First difference between them comes in terms of  speed.  HashSet is fastest, LinkedHashSet is second on performance or almost similar to HashSet but TreeSet is bit slower because of sorting operation it needs to perform on each insertion. TreeSet provides guaranteed O(log(n)) time for common operations like add, remove and contains, while HashSet and LinkedHashSet offer constant time performance e.g. O(1) for add, contains and remove given hash function uniformly distribute elements in bucket.

Ordering : HashSet does not maintain any order while LinkedHashSet maintains insertion order of elements much like List interface and TreeSet maintains sorting order or elements.

Internal Implementation : HashSet is backed by an HashMap instance, LinkedHashSet is implemented using HashSet and LinkedList while TreeSet is backed up by NavigableMap in Java and by default it uses TreeMap.

null : Both HashSet and LinkedHashSet allows null but TreeSet doesn't allow null but TreeSet doesn't allow null and throw java.lang.NullPointerException when you will insert null into TreeSet. Since TreeSet uses compareTo() method of respective elements to compare them  which throws NullPointerException while comparing with null, here is an example:

TreeSet cities

Exception in thread "main" java.lang.NullPointerException

        at java.lang.String.compareTo(String.java:1167)

        at java.lang.String.compareTo(String.java:92)

        at java.util.TreeMap.put(TreeMap.java:545)

        at java.util.TreeSet.add(TreeSet.java:238)

Comparison : HashSet and LinkedHashSet uses equals() method in Java for comparison but TreeSet uses compareTo() method for maintaining ordering. That's why compareTo() should be consistent to equals in Java. failing to do so break general contact of Set interface i.e. it can permit duplicates.

TreeSet vs HashSet vs LinkedHashSet - Example

Let’s compare all these Set implementation on some points by writing Java program. In this example we are demonstrating difference in ordering, time taking while inserting 1M records among TreeSet, HashSet and LinkedHashSet in Java. This will help to solidify some points which discussed in earlier section and help to decide when to use HashSet, LinkedHashSet or TreeSet in Java.

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;

/**
 * Java program to demonstrate difference between TreeSet, HashSet and LinkedHashSet

 * in Java Collection.
 * @author
 */
public class SetComparision {
 
    public static void main(String args[]){            
        HashSet<String> fruitsStore = new HashSet<String>();
        LinkedHashSet<String> fruitMarket = new LinkedHashSet<String>();
        TreeSet<String> fruitBuzz = new TreeSet<String>();
     
        for(String fruit: Arrays.asList("mango", "apple", "banana")){
            fruitsStore.add(fruit);
            fruitMarket.add(fruit);
            fruitBuzz.add(fruit);
        }
       

        //no ordering in HashSet – elements stored in random order
        System.out.println("Ordering in HashSet :" + fruitsStore);

        //insertion order or elements – LinkedHashSet storeds elements as insertion
        System.err.println("Order of element in LinkedHashSet :" + fruitMarket);

        //should be sorted order – TreeSet stores element in sorted order
        System.out.println("Order of objects in TreeSet :" + fruitBuzz); 

     

        //Performance test to insert 10M elements in HashSet, LinkedHashSet and TreeSet
        Set<Integer> numbers = new HashSet<Integer>();
        long startTime = System.nanoTime();
        for(int i =0; i<10000000; i++){
            numbers.add(i);
        }

        long endTime = System.nanoTime();
        System.out.println("Total time to insert 10M elements in HashSet in sec : "

                            + (endTime - startTime));
     
     
        // LinkedHashSet performance Test – inserting 10M objects

        numbers = new LinkedHashSet<Integer>();
        startTime = System.nanoTime();
        for(int i =0; i<10000000; i++){
            numbers.add(i);
        }
        endTime = System.nanoTime();
        System.out.println("Total time to insert 10M elements in LinkedHashSet in sec : "

                            + (endTime - startTime));
       

        // TreeSet performance Test – inserting 10M objects
        numbers = new TreeSet<Integer>();
        startTime = System.nanoTime();
        for(int i =0; i<10000000; i++){
            numbers.add(i);
        }
        endTime = System.nanoTime();
        System.out.println("Total time to insert 10M elements in TreeSet in sec : "

                            + (endTime - startTime));
    }
}

Output
Ordering in HashSet :[banana, apple, mango]
Order of element in LinkedHashSet :[mango, apple, banana]
Order of objects in TreeSet :[apple, banana, mango]
Total time to insert 10M elements in HashSet in sec : 3564570637
Total time to insert 10M elements in LinkedHashSet in sec : 3511277551
Total time to insert 10M elements in TreeSet in sec : 10968043705

When to use HashSet, TreeSet and LinkedHashSet in Java

Since all three implements Set interface they can be used for common Set operations like not allowing duplicates but since HashSet, TreeSet and LinkedHashSet has there special feature which makes them appropriate in certain scenario. Because of sorting order provided by TreeSet, use TreeSet when you need a collection where elements are sorted without duplicates. HashSet are rather general purpose Set implementation, Use it as default Set implementation if you need a fast, duplicate free collection. LinkedHashSet is extension of HashSet and its more suitable where you need to maintain insertion order of elements, similar to List without compromising performance for costly TreeSet. Another use of LinkedHashSet is for creating copies of existing Set, Since LinkedHashSet preservers insertion order, it returns Set which contains same elements in same order like exact copy. In short,  although all three are Set interface implementation they offer distinctive feature, HashSet is a general purpose Set while LinkedHashSet provides insertion order guarantee and TreeSet is a SortedSet which stores elements in sorted order specified by Comparator or Comparable in Java.

How to copy object from one Set to other

Here is code example of LinkedHashSet which demonstrate How LinkedHashSet can be used to copy objects from one Set to another without losing order. You will get exact replica of source Set, in terms of contents and order. Here static method copy(Set source) is written using Generics, This kind of parameterized method provides type-safety and help to avoid ClassCastException at runtime.

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;

/**
 * Java program to copy object from one HashSet to another using LinkedHashSet.
 * LinkedHashSet preserves order of element while copying elements.
 *
 * @author Javin
 */
public class SetUtils{
   
    public static void main(String args[]) {
       
        HashSet<String> source = new HashSet<String>(Arrays.asList("Set, List, Map"));
        System.out.println("source : " + source);
        Set<String> copy = SetUtils.copy(source);
        System.out.println("copy of HashSet using LinkedHashSet: " + copy);
    }
   
    /*
     * Static utility method to copy Set in Java
     */
    public static <T> Set<T> copy(Set<T> source){
           return new LinkedHashSet<T>(source);
    }
}
Output:
source : [Set, List, Map]
copy of HashSet using LinkedHashSet: [Set, List, Map]

Always code for interface than implementation so that you can replace HashSet to LinkedHashSet or TreeSet when your requirement changes. That’s all on difference between HashSet, LinkedHashSet and TreeSet in Java.  If you know any other significant difference between TreeSet, LinkedHashSet and HashSet which is worth remembering than please add as comment.

Other tutorials from Java Collection Framework

How to sort ArrayList in descending order in Java

4 ways to loop Map in Java with examples

How to convert List to Array in Java

How to create read only or unmodifiable Collection in Java

How to convert Collection to coma separated String in Java

10 example of Hashtable in Java - tutorial