Set Interface: HashSet, LinkedHashSet, TreeSet

A Set is a collection that guarantees no duplicate elements — attempting to add an element that is already present (as determined by equals()) is silently ignored, and add() returns false. Java provides three principal implementations, and the one you choose determines what, if any, ordering guarantee you get.

Why it matters

A Set answers the question "have I seen this before?" in constant time, which a list cannot do. Removing duplicates, checking membership and finding what two groups have in common are all set operations. The three implementations differ only in the order they give back the elements and in what that order costs.

HashSet — No Order, Hash-Based

HashSet stores elements in a hash table and gives no guarantee about iteration order — the order can even change between runs. In exchange, add(), remove(), and contains() run in average O(1) time, because the element's hash code determines which bucket it belongs to directly. HashSet requires that elements have correct, consistent hashCode() and equals() implementations; getting these wrong breaks uniqueness silently.

LinkedHashSet — Insertion Order Preserved

LinkedHashSet extends HashSet but additionally maintains a doubly linked list running through all entries, so iteration order matches insertion order. It costs slightly more memory and a small constant-time overhead compared to HashSet, but is still O(1) average for the core operations. Choose it when you need set semantics (no duplicates) but also want predictable, reproducible iteration order.

TreeSet — Sorted Order

TreeSet is backed by a red-black tree and keeps its elements in sorted order at all times. Core operations (add, remove, contains) run in O(log n) time — slower than a hash-based set, but you gain sorted iteration plus navigation methods like first(), last(), higher(), and lower(). TreeSet requires that elements either implement Comparable, or that you supply a Comparator when constructing it — otherwise it throws ClassCastException at runtime on the first comparison.

• HashSet: no ordering guarantee, O(1) average, needs correct hashCode/equals.
• LinkedHashSet: insertion order preserved, O(1) average, slightly more overhead than HashSet.
• TreeSet: sorted order, O(log n), requires Comparable or a Comparator.

Time complexity

Example

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

public class SetDemo {
    public static void main(String[] args) {
        Set<String> hashSet = new HashSet<>();
        hashSet.add("banana");
        hashSet.add("apple");
        hashSet.add("cherry");
        System.out.println("HashSet (unordered): " + hashSet);

        Set<String> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add("banana");
        linkedHashSet.add("apple");
        linkedHashSet.add("cherry");
        System.out.println("LinkedHashSet (insertion order): " + linkedHashSet);

        Set<String> treeSet = new TreeSet<>();
        treeSet.add("banana");
        treeSet.add("apple");
        treeSet.add("cherry");
        System.out.println("TreeSet (sorted order): " + treeSet);
    }
}

HashSet (unordered): [banana, apple, cherry]
LinkedHashSet (insertion order): [banana, apple, cherry]
TreeSet (sorted order): [apple, banana, cherry]

Exercise

Print the first colour that appears a second time in the list. Use the value that add returns instead of calling contains first.

Expected output: blue

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class FirstDuplicate {
    public static void main(String[] args) {
        List<String> colours = List.of("red", "blue", "green", "blue", "red");
        Set<String> seen = new HashSet<>();

        for (String colour : colours) {
            // TODO: add the colour to the set; if it was already there, print it and stop
        }
    }
}

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class FirstDuplicate {
    public static void main(String[] args) {
        List<String> colours = List.of("red", "blue", "green", "blue", "red");
        Set<String> seen = new HashSet<>();

        for (String colour : colours) {
            if (!seen.add(colour)) { // false means it was already in the set
                System.out.println(colour); // blue
                break;
            }
        }
    }
}

Quick quiz

Interview questions