HashSet vs LinkedHashSet vs TreeSet in Java

Hey everyone, welcome back to my blog! In today’s blog post, we’ll be comparing three important implementations of the Set interface in Java—HashSet, LinkedHashSet, and TreeSet. While all three are used to store unique elements, they behave differently in terms of performance, ordering, and structure. Let’s dive into the differences and see some examples in action!

HashSet vs LinkedHashSet vs TreeSet in Java

1. Difference 1: Internal Data Structure

The first major difference is the internal data structure each of these classes uses to store elements. HashSet uses a hash table to store its elements, which gives it fast performance for common operations. LinkedHashSet also uses a hash table but adds a doubly linked list to maintain insertion order. TreeSet, on the other hand, uses a red-black tree, which is a self-balancing binary search tree, to store its elements in sorted order.

Example:

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

public class SetComparison {
    public static void main(String[] args) {
        // HashSet example
        Set<String> hashSet = new HashSet<>();
        hashSet.add("Banana");
        hashSet.add("Apple");
        hashSet.add("Cherry");
        System.out.println("HashSet Output: " + hashSet);

        // LinkedHashSet example
        Set<String> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add("Banana");
        linkedHashSet.add("Apple");
        linkedHashSet.add("Cherry");
        System.out.println("LinkedHashSet Output: " + linkedHashSet);

        // TreeSet example
        Set<String> treeSet = new TreeSet<>();
        treeSet.add("Banana");
        treeSet.add("Apple");
        treeSet.add("Cherry");
        System.out.println("TreeSet Output: " + treeSet);
    }
}

Output:

HashSet Output: [Banana, Apple, Cherry] or [Apple, Cherry, Banana] (order is unpredictable)
LinkedHashSet Output: [Banana, Apple, Cherry] (insertion order maintained)
TreeSet Output: [Apple, Banana, Cherry] (sorted order)

2. Difference 2: Order of Elements

When it comes to ordering, HashSet does not maintain any particular order of elements—its order is unpredictable. LinkedHashSet preserves the order in which elements are inserted, so when you iterate over it, the elements appear in that same order. TreeSet, on the other hand, automatically sorts the elements in their natural order (or using a custom comparator if provided).

Example:

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

public class SetOrderComparison {
    public static void main(String[] args) {
        // HashSet example
        Set<Integer> hashSet = new HashSet<>();
        hashSet.add(50);
        hashSet.add(10);
        hashSet.add(30);
        System.out.println("HashSet Output: " + hashSet); // Unordered

        // LinkedHashSet example
        Set<Integer> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add(50);
        linkedHashSet.add(10);
        linkedHashSet.add(30);
        System.out.println("LinkedHashSet Output: " + linkedHashSet); // Preserves insertion order

        // TreeSet example
        Set<Integer> treeSet = new TreeSet<>();
        treeSet.add(50);
        treeSet.add(10);
        treeSet.add(30);
        System.out.println("TreeSet Output: " + treeSet); // Sorted order
    }
}

Output:

HashSet Output: [50, 10, 30] or any random order
LinkedHashSet Output: [50, 10, 30] (insertion order)
TreeSet Output: [10, 30, 50] (sorted order)

3. Difference 3: Performance

In terms of performance, HashSet is the fastest because it uses a hash table and doesn’t have to worry about maintaining order. Most operations like adding, removing, and checking if an element exists take constant time, O(1). LinkedHashSet is slightly slower than HashSet because it has the overhead of maintaining the insertion order using a linked list. TreeSet is the slowest because it has to maintain elements in sorted order, and its operations take O(log n) time.

Example:

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

public class SetPerformanceComparison {
    public static void main(String[] args) {
        // HashSet example
        Set<Integer> hashSet = new HashSet<>();
        long startTime = System.nanoTime();
        hashSet.add(100);
        hashSet.add(200);
        hashSet.add(300);
        System.out.println("HashSet contains 200: " + hashSet.contains(200));
        long endTime = System.nanoTime();
        System.out.println("HashSet operation time: " + (endTime - startTime) + " ns");

        // LinkedHashSet example
        Set<Integer> linkedHashSet = new LinkedHashSet<>();
        startTime = System.nanoTime();
        linkedHashSet.add(100);
        linkedHashSet.add(200);
        linkedHashSet.add(300);
        System.out.println("LinkedHashSet contains 200: " + linkedHashSet.contains(200));
        endTime = System.nanoTime();
        System.out.println("LinkedHashSet operation time: " + (endTime - startTime) + " ns");

        // TreeSet example
        Set<Integer> treeSet = new TreeSet<>();
        startTime = System.nanoTime();
        treeSet.add(100);
        treeSet.add(200);
        treeSet.add(300);
        System.out.println("TreeSet contains 200: " + treeSet.contains(200));
        endTime = System.nanoTime();
        System.out.println("TreeSet operation time: " + (endTime - startTime) + " ns");
    }
}

Output:

HashSet contains 200: true
HashSet operation time: [Shorter time in nanoseconds]

LinkedHashSet contains 200: true
LinkedHashSet operation time: [Slightly longer time in nanoseconds]

TreeSet contains 200: true
TreeSet operation time: [Longest time in nanoseconds due to sorting]

4. Difference 4: Null Elements

Another important difference is how they handle null elements. HashSet allows one null element to be added, since it can store any type of object, including null. LinkedHashSet also allows one null element. However, TreeSet does not allow null elements because it needs to compare elements to maintain the sorted order, and null cannot be compared with other objects, leading to a NullPointerException.

Example:

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

public class SetNullComparison {
    public static void main(String[] args) {
        // HashSet example - allows null
        Set<String> hashSet = new HashSet<>();
        hashSet.add(null);
        hashSet.add("Banana");
        System.out.println("HashSet with null: " + hashSet);

        // LinkedHashSet example - allows null
        Set<String> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add(null);
        linkedHashSet.add("Banana");
        System.out.println("LinkedHashSet with null: " + linkedHashSet);

        // TreeSet example - does not allow null
        Set<String> treeSet = new TreeSet<>();
        try {
            treeSet.add(null); // This will throw a NullPointerException
        } catch (NullPointerException e) {
            System.out.println("TreeSet does not allow null values");
        }
    }
}

Output:

HashSet with null: [null, Banana]
LinkedHashSet with null: [null, Banana]
TreeSet does not allow null values

Conclusion

That’s it for today’s comparison of HashSet, LinkedHashSet, and TreeSet! To sum up: HashSet is great when you don’t care about the order of elements and need fast performance. LinkedHashSet is useful when you want to preserve the order in which elements are inserted. TreeSet is perfect when you need to maintain elements in sorted order. Try running these examples in your IDE and see how they behave.

Summary Table: HashSet vs LinkedHashSet vs TreeSet