Collections

64. Set Implementations Compared

HashSet is the default O(1) unordered set; LinkedHashSet maintains insertion order; TreeSet maintains sorted order (O(log n)); all three have different null and thread-safety characteristics.

Java 21 (core language)

Explanation

HashSet<E> is backed by a HashMap<E, Object>. Operations are O(1) average (O(n) worst case with hash collisions, mitigated by treeification since Java 8). Allows one null element. Iteration order is unpredictable.

LinkedHashSet<E> extends HashSet with a linked list tracking insertion order. Iteration is in insertion order. Slightly more memory and marginally slower than HashSet due to the linked-list maintenance.

TreeSet<E> uses a red-black tree (TreeMap internally). Operations are O(log n). Elements must be Comparable or you must provide a Comparator. Does not allow null (throws NullPointerException). Provides first(), last(), headSet(to), tailSet(from), subSet(from, to) range views.

None of the three are thread-safe. For concurrent use: Collections.newSetFromMap(new ConcurrentHashMap<>()).

Example

import java.util.*;

public class SetImplementations {
    public static void main(String[] args) {
        // HashSet: fast, no ordering guarantee
        Set<String> hash = new HashSet<>(Set.of("banana", "apple", "cherry", "apple"));
        System.out.println("HashSet size: " + hash.size()); // 3 (deduped)
        System.out.println("Contains apple: " + hash.contains("apple")); // O(1)
        System.out.println("HashSet: " + hash); // order unpredictable

        // LinkedHashSet: insertion order
        Set<String> linked = new LinkedHashSet<>(List.of("banana", "apple", "cherry", "apple"));
        System.out.println("LinkedHashSet: " + linked); // [banana, apple, cherry]

        // TreeSet: sorted order
        TreeSet<String> tree = new TreeSet<>(List.of("banana", "apple", "cherry"));
        System.out.println("TreeSet: " + tree); // [apple, banana, cherry]
        System.out.println("First: " + tree.first());  // apple
        System.out.println("Last:  " + tree.last());   // cherry
        System.out.println("Head(<cherry): " + tree.headSet("cherry")); // [apple, banana]

        // TreeSet with custom Comparator
        TreeSet<String> byLength = new TreeSet<>(
            Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));
        byLength.addAll(List.of("banana", "apple", "kiwi", "fig", "cherry"));
        System.out.println("By length: " + byLength);

        // null handling
        hash.add(null); // OK for HashSet
        System.out.println("HashSet with null: " + hash.contains(null));
        try {
            tree.add(null); // NullPointerException for TreeSet
        } catch (NullPointerException e) {
            System.out.println("TreeSet rejects null");
        }
    }
}

Sources