HashSet vs TreeSet vs LinkedHashSet in Java

HashSet vs TreeSet vs LinkedHashSet in Java

Java provides several implementations of the Set interface to store unique elements efficiently. The most commonly used Set implementations are:

HashSet – Uses a hash table for storage.
TreeSet – Uses a red-black tree to maintain sorted order.
LinkedHashSet – Maintains insertion order while using a hash table.

Each of these implementations has distinct characteristics, affecting performance and behavior. In this blog post, we will explore the differences between HashSet, TreeSet, and LinkedHashSet and guide you on when to use each.

1. HashSet

A HashSet is a collection that does not allow duplicate elements and does not guarantee any order of elements. It is backed by a hash table, which provides efficient add, remove, and lookup operations.

Characteristics of HashSet:

Unordered collection (elements are not stored in any predictable order).
Allows null values (but only one).
Fast insertion, deletion, and search operations (O(1) on average).

Example of HashSet Usage:

import java.util.*;

public class HashSetExample {
    public static void main(String[] args) {
        Set<String> hashSet = new HashSet<>();
        hashSet.add("Banana");
        hashSet.add("Apple");
        hashSet.add("Cherry");
        hashSet.add("Apple"); // Duplicate is ignored

        System.out.println(hashSet); // Output: [Apple, Cherry, Banana] (order may vary)
    }
}

2. TreeSet

A TreeSet is a Set implementation that stores elements in sorted order. It is backed by a red-black tree, which ensures that elements remain sorted at all times.

Characteristics of TreeSet:

Elements are stored in sorted order (natural order or via comparator).
Does not allow null values (throws NullPointerException).
Slower insertion and deletion than HashSet (O(log n)).
Faster retrieval of sorted elements.

Example of TreeSet Usage:

import java.util.*;

public class TreeSetExample {
    public static void main(String[] args) {
        Set<String> treeSet = new TreeSet<>();
        treeSet.add("Banana");
        treeSet.add("Apple");
        treeSet.add("Cherry");
        
        System.out.println(treeSet); // Output: [Apple, Banana, Cherry] (sorted order)
    }
}

3. LinkedHashSet

A LinkedHashSet maintains the insertion order of elements while providing fast lookup operations similar to HashSet. It internally uses a linked list with a hash table.

Characteristics of LinkedHashSet:

Maintains insertion order.
Allows null values.
Slower than HashSet but faster than TreeSet.
Useful when predictable iteration order is required.

Example of LinkedHashSet Usage:

import java.util.*;

public class LinkedHashSetExample {
    public static void main(String[] args) {
        Set<String> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add("Banana");
        linkedHashSet.add("Apple");
        linkedHashSet.add("Cherry");
        
        System.out.println(linkedHashSet); // Output: [Banana, Apple, Cherry] (insertion order)
    }
}

Performance Comparison: HashSet vs TreeSet vs LinkedHashSet

Feature	HashSet	TreeSet	LinkedHashSet
Ordering	No order	Sorted order	Insertion order
Null values	Allowed	Not allowed	Allowed
Insertion Time Complexity	O(1)	O(log n)	O(1)
Deletion Time Complexity	O(1)	O(log n)	O(1)
Search Time Complexity	O(1)	O(log n)	O(1)
Memory Usage	Least	Most	More than HashSet but less than TreeSet

When to Use HashSet, TreeSet, or LinkedHashSet?

Scenario	Recommended Collection
Need fast lookups and don't care about order	`HashSet`
Need sorted elements	`TreeSet`
Need to maintain insertion order	`LinkedHashSet`
Need high performance and no duplicate elements	`HashSet`
Need a sorted set for navigation (e.g., first, last, subset)	`TreeSet`
Need both fast lookups and ordered elements	`LinkedHashSet`

Example: Performance Test

Let's compare the time taken for insertion into HashSet, TreeSet, and LinkedHashSet.

import java.util.*;

public class SetPerformanceTest {
    public static void main(String[] args) {
        int size = 100000;
        Set<Integer> hashSet = new HashSet<>();
        Set<Integer> treeSet = new TreeSet<>();
        Set<Integer> linkedHashSet = new LinkedHashSet<>();
        
        long startTime, endTime;
        
        // HashSet Insertion Test
        startTime = System.nanoTime();
        for (int i = 0; i < size; i++) {
            hashSet.add(i);
        }
        endTime = System.nanoTime();
        System.out.println("HashSet Insertion Time: " + (endTime - startTime) + " ns");

        // TreeSet Insertion Test
        startTime = System.nanoTime();
        for (int i = 0; i < size; i++) {
            treeSet.add(i);
        }
        endTime = System.nanoTime();
        System.out.println("TreeSet Insertion Time: " + (endTime - startTime) + " ns");
        
        // LinkedHashSet Insertion Test
        startTime = System.nanoTime();
        for (int i = 0; i < size; i++) {
            linkedHashSet.add(i);
        }
        endTime = System.nanoTime();
        System.out.println("LinkedHashSet Insertion Time: " + (endTime - startTime) + " ns");
    }
}