HashSet & TreeSet

HashSet

HashSet is the most commonly used Set implementation. It is backed by a HashMap internally — each element is stored as a key in the HashMap with a dummy value.

Key characteristics:

• Backed by HashMap
• O(1) average for add, remove, contains
• No ordering guarantees
• Allows one null element
• Not synchronized (not thread-safe)

import java.util.*;

public class HashSetDemo {
    public static void main(String[] args) {
        // Creating HashSet
        Set<String> colors = new HashSet<>();

        // Adding elements
        colors.add("Red");
        colors.add("Green");
        colors.add("Blue");
        colors.add("Red"); // duplicate - ignored
        colors.add(null); // one null allowed
        System.out.println("Set: " + colors); // order not guaranteed
        System.out.println("Size: " + colors.size()); // 4, not 5

        // Checking membership
        System.out.println("Contains Red: " + colors.contains("Red")); // true
        System.out.println("Contains Yellow: " + colors.contains("Yellow")); // false

        // Removing elements
        colors.remove("Blue");
        colors.remove("Yellow"); // no-op if not present
        System.out.println("After remove: " + colors);

        // Iterating
        for (String color : colors) {
            System.out.println("Color: " + color);
        }

        // Set operations
        Set<Integer> setA = new HashSet<>(Arrays.asList(1, 2, 3, 4));
        Set<Integer> setB = new HashSet<>(Arrays.asList(3, 4, 5, 6));

        // Union
        Set<Integer> union = new HashSet<>(setA);
        union.addAll(setB);
        System.out.println("\nUnion: " + union); // [1, 2, 3, 4, 5, 6]

        // Intersection
        Set<Integer> intersection = new HashSet<>(setA);
        intersection.retainAll(setB);
        System.out.println("Intersection: " + intersection); // [3, 4]

        // Difference (A - B)
        Set<Integer> difference = new HashSet<>(setA);
        difference.removeAll(setB);
        System.out.println("Difference (A-B): " + difference); // [1, 2]

        // Converting between collections
        List<String> list = Arrays.asList("a", "b", "a", "c");
        Set<String> unique = new HashSet<>(list); // remove duplicates
        System.out.println("\nUnique from list: " + unique);

        List<String> backToList = new ArrayList<>(unique);
        System.out.println("Back to list: " + backToList);
    }
}

Internal implementation: HashSet uses a HashMap where elements are keys and values are a shared dummy object:

// Simplified internal structure
// HashSet.add(e) is equivalent to:
// map.put(e, PRESENT)
// where PRESENT is a static final Object

This means HashSet inherits HashMap's performance characteristics: O(1) average for add/remove/contains, with occasional O(n) worst case for hash collisions.

TreeSet

TreeSet is a NavigableSet backed by a TreeMap (red-black tree). It keeps elements in sorted order and provides navigation methods.

Key characteristics:

• Backed by TreeMap
• O(log n) for add, remove, contains
• Elements sorted by natural ordering or Comparator
• No null elements (throws NullPointerException)
• NavigableSet methods for finding nearest elements

import java.util.*;

public class TreeSetDemo {
    public static void main(String[] args) {
        // Natural ordering
        TreeSet<Integer> numbers = new TreeSet<>();
        numbers.add(30);
        numbers.add(10);
        numbers.add(50);
        numbers.add(20);
        numbers.add(40);
        System.out.println("Sorted: " + numbers); // [10, 20, 30, 40, 50]

        // Navigation methods
        System.out.println("First: " + numbers.first()); // 10
        System.out.println("Last: " + numbers.last()); // 50
        System.out.println("Lower(30): " + numbers.lower(30)); // 20
        System.out.println("Higher(30): " + numbers.higher(30)); // 40
        System.out.println("Floor(25): " + numbers.floor(25)); // 20
        System.out.println("Ceiling(25): " + numbers.ceiling(25)); // 30

        // Subset views
        System.out.println("HeadSet(30): " + numbers.headSet(30)); // [10, 20]
        System.out.println("TailSet(30): " + numbers.tailSet(30)); // [30, 40, 50]
        System.out.println("SubSet(20,40): " + numbers.subSet(20, 40)); // [20, 30]

        // Custom ordering with Comparator
        TreeSet<String> byLength = new TreeSet<>(Comparator.comparingInt(String::length)
                .thenComparing(Comparator.naturalOrder()));
        byLength.add("Banana");
        byLength.add("Apple");
        byLength.add("Cherry");
        byLength.add("Fig");
        byLength.add("Kiwi");
        System.out.println("\nBy length: " + byLength); // [Fig, Kiwi, Apple, Banana, Cherry]

        // Descending iteration
        System.out.println("Descending: " + numbers.descendingSet()); // [50, 40, 30, 20, 10]

        // Poll (remove while accessing)
        System.out.println("pollFirst: " + numbers.pollFirst()); // 10
        System.out.println("pollLast: " + numbers.pollLast()); // 50
        System.out.println("After polls: " + numbers); // [20, 30, 40]

        // Set operations with TreeSet
        TreeSet<Integer> setA = new TreeSet<>(Arrays.asList(1, 2, 3, 4, 5));
        TreeSet<Integer> setB = new TreeSet<>(Arrays.asList(3, 4, 5, 6, 7));
        System.out.println("\nUnion: " + union(setA, setB));
        System.out.println("Intersection: " + intersection(setA, setB));
    }

    public static <T> TreeSet<T> union(TreeSet<T> a, TreeSet<T> b) {
        TreeSet<T> result = new TreeSet<>(a);
        result.addAll(b);
        return result;
    }

    public static <T> TreeSet<T> intersection(TreeSet<T> a, TreeSet<T> b) {
        TreeSet<T> result = new TreeSet<>(a);
        result.retainAll(b);
        return result;
    }
}

When to use TreeSet:

• You need sorted unique elements
• You need navigation methods (lower, higher, floor, ceiling)
• You need range views (headSet, tailSet, subSet)
• You need the smallest or largest element efficiently

LinkedHashSet

LinkedHashSet extends HashSet and maintains a doubly linked list across all elements. This preserves insertion order while maintaining O(1) average operations.

Key characteristics:

• Maintains insertion order
• O(1) average for add, remove, contains
• Slightly more memory than HashSet (linked list overhead)
• Slightly slower than HashSet due to maintaining linked list

import java.util.*;

public class LinkedHashSetDemo {
    public static void main(String[] args) {
        // Insertion order preserved
        LinkedHashSet<String> ordered = new LinkedHashSet<>();
        ordered.add("Banana");
        ordered.add("Apple");
        ordered.add("Cherry");
        ordered.add("Date");
        ordered.add("Banana"); // duplicate - ignored

        System.out.println("LinkedHashSet: " + ordered);
        // [Banana, Apple, Cherry, Date] - insertion order

        // Compare with HashSet
        Set<String> unordered = new HashSet<>();
        unordered.add("Banana");
        unordered.add("Apple");
        unordered.add("Cherry");
        unordered.add("Date");
        System.out.println("HashSet: " + unordered); // order not guaranteed

        // Useful for removing duplicates while preserving order
        List<String> listWithDuplicates = Arrays.asList(
            "Charlie", "Alice", "Bob", "Alice", "Charlie", "David"
        );
        LinkedHashSet<String> uniqueOrdered = new LinkedHashSet<>(listWithDuplicates);
        List<String> result = new ArrayList<>(uniqueOrdered);
        System.out.println("\nOriginal: " + listWithDuplicates);
        System.out.println("Unique ordered: " + result);
        // [Charlie, Alice, Bob, David] - no duplicates, insertion order

        // Iterating in insertion order
        System.out.println("\nIterating:");
        for (String s : uniqueOrdered) {
            System.out.println("  " + s);
        }

        // Set operations preserving order
        LinkedHashSet<Integer> setA = new LinkedHashSet<>(Arrays.asList(1, 2, 3));
        LinkedHashSet<Integer> setB = new LinkedHashSet<>(Arrays.asList(3, 4, 5));
        LinkedHashSet<Integer> union = new LinkedHashSet<>(setA);
        union.addAll(setB);
        System.out.println("\nUnion (ordered): " + union); // [1, 2, 3, 4, 5]
    }
}

When to use LinkedHashSet:

• You need uniqueness with insertion order
• You want to remove duplicates from a list while preserving order
• You want predictable iteration order without sorting
• You want better performance than TreeSet but with ordering

Set Operations and Time Complexity

Set operations:

• addAll() — Union: O(n + m)
• retainAll() — Intersection: O(n * m)
• removeAll() — Difference: O(n * m)

import java.util.*;

public class SetOperationsDemo {
    public static void main(String[] args) {
        Set<Integer> setA = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
        Set<Integer> setB = new HashSet<>(Arrays.asList(4, 5, 6, 7, 8));

        // Union: A ∪ B
        Set<Integer> union = new HashSet<>(setA);
        union.addAll(setB);
        System.out.println("Union: " + union); // [1, 2, 3, 4, 5, 6, 7, 8]

        // Intersection: A ∩ B
        Set<Integer> intersection = new HashSet<>(setA);
        intersection.retainAll(setB);
        System.out.println("Intersection: " + intersection); // [4, 5]

        // Difference: A - B
        Set<Integer> diffAB = new HashSet<>(setA);
        diffAB.removeAll(setB);
        System.out.println("A - B: " + diffAB); // [1, 2, 3]

        // Difference: B - A
        Set<Integer> diffBA = new HashSet<>(setB);
        diffBA.removeAll(setA);
        System.out.println("B - A: " + diffBA); // [6, 7, 8]

        // Symmetric Difference: (A - B) ∪ (B - A)
        Set<Integer> symDiff = new HashSet<>(setA);
        symDiff.addAll(setB);
        Set<Integer> common = new HashSet<>(setA);
        common.retainAll(setB);
        symDiff.removeAll(common);
        System.out.println("Symmetric Diff: " + symDiff); // [1, 2, 3, 6, 7, 8]

        // Subset check
        Set<Integer> subset = new HashSet<>(Arrays.asList(1, 2, 3));
        System.out.println("Is subset? " + setA.containsAll(subset)); // true

        // Performance demonstration
        Set<Integer> large = new HashSet<>();
        for (int i = 0; i < 100000; i++) {
            large.add(i);
        }
        long start = System.nanoTime();
        large.contains(50000); // O(1)
        long time = System.nanoTime() - start;
        System.out.println("\nHashSet contains: " + time + " ns");

        // Converting between Set types
        Set<String> linked = new LinkedHashSet<>(Arrays.asList("c", "a", "b"));
        Set<String> tree = new TreeSet<>(linked); // sorted
        Set<String> hash = new HashSet<>(tree); // unordered
        System.out.println("Linked: " + linked); // [c, a, b]
        System.out.println("Tree: " + tree); // [a, b, c]
        System.out.println("Hash: " + hash); // [a, b, c] (order not guaranteed)
    }
}

Performance tips:

• Use addAll/retainAll/removeAll for bulk operations
• For intersection, iterate over the smaller set: smallSet.retainAll(largeSet)
• HashSet is fastest for general-purpose use
• Use LinkedHashSet when order matters
• Use TreeSet when sorted order or navigation is needed