Set Interface in Java: HashSet, LinkedHashSet, TreeSet

Every time you deduplicate user IDs, track visited nodes in a graph problem, or enforce "this email is already registered", you are reaching for a Set. The interface itself is tiny — the real skill is choosing between HashSet, LinkedHashSet and TreeSet, because they make three different promises about ordering and pay three different performance prices. This page gives you the decision framework.

What the Set contract says

java.util.Set extends Collection and adds exactly one rule: no duplicates. Formally, a set never contains two elements a and b where a.equals(b). Beyond that, the interface adds almost no new methods — the semantics do the work:

• add(e) returns false (and changes nothing) if an equal element already exists.
• There is no get(int index). Sets have no positions — that is List territory.
• contains(e) is the star method, and its speed depends entirely on the implementation.

That boolean return from add is genuinely useful — it tells you "was this new?" in one call:

Set<String> seen = new HashSet<>();
if (!seen.add(email)) {
    System.out.println("Duplicate registration attempt: " + email);
}

The three implementations and their promises

Under the hood, HashSet is literally a HashMap whose keys are your elements; LinkedHashSet threads a doubly-linked list through those entries to remember insertion order; TreeSet delegates to a TreeMap, a self-balancing red-black tree.

Here is the ordering difference, runnable:

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

public class SetOrdering {
    public static void main(String[] args) {
        String[] cities = {"Hyderabad", "Chennai", "Bengaluru", "Pune", "Chennai"};

        Set<String> hash   = new HashSet<>();
        Set<String> linked = new LinkedHashSet<>();
        Set<String> tree   = new TreeSet<>();

        for (String c : cities) {
            hash.add(c); linked.add(c); tree.add(c);
        }

        System.out.println("HashSet       : " + hash);
        // e.g. [Chennai, Pune, Bengaluru, Hyderabad] — no promised order
        System.out.println("LinkedHashSet : " + linked);
        // [Hyderabad, Chennai, Bengaluru, Pune]     — insertion order
        System.out.println("TreeSet       : " + tree);
        // [Bengaluru, Chennai, Hyderabad, Pune]     — sorted order
    }
}

All three silently ignored the duplicate "Chennai". Only the iteration order differs — and that single difference should usually drive your choice.

What the complexity difference means in practice

The O(1) versus O(log n) gap is smaller than it looks for everyday sizes. On a set of one million elements, a TreeSet lookup walks a tree roughly 20 levels deep — about 20 comparisons — while a HashSet does one hash computation and usually one equals call. Both feel instant in isolation; the gap matters when the operation sits inside a hot loop running millions of times. LinkedHashSet costs almost the same as HashSet per operation, but each entry carries two extra references to maintain the insertion-order list, so memory grows accordingly. The practical rule: pick the ordering guarantee you need first, and only worry about the constant factors when a profiler tells you to.

Common mistake: A common mistake beginners make is relying on the order a HashSet happens to print during testing. That order can change when the set resizes or between JVM runs. If any code depends on iteration order, HashSet is the wrong type — use LinkedHashSet or TreeSet and make the promise explicit.

How Sets detect duplicates (and why it breaks)

Hash-based sets run a two-step check on add: compute hashCode() to locate a bucket, then call equals() against elements in that bucket. Your element class must override both consistently — equal objects must produce equal hash codes. Break that rule and the set quietly accepts duplicates:

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

class Student {
    final String rollNo;
    Student(String rollNo) { this.rollNo = rollNo; }

    @Override public boolean equals(Object o) {
        return o instanceof Student s && rollNo.equals(s.rollNo);
    }
    @Override public int hashCode() {
        return Objects.hash(rollNo);   // comment this out and watch duplicates appear
    }
}

public class DuplicateCheck {
    public static void main(String[] args) {
        Set<Student> batch = new HashSet<>();
        batch.add(new Student("CB-101"));
        batch.add(new Student("CB-101"));   // rejected: equal + same hash
        System.out.println(batch.size());   // 1
    }
}

Delete the hashCode override and size() prints 2: the two objects land in different buckets, so equals is never even consulted.

TreeSet plays by a different rulebook: it ignores equals entirely and treats compareTo(...) == 0 (or Comparator returning 0) as "duplicate". A Comparator that compares only by salary will keep just one employee per salary value, even if they are different people by equals.

Interview note: "HashSet uses equals; TreeSet uses compareTo" is a favorite trap. If your Comparator returns 0 for objects that are not equals-equal, TreeSet drops elements a HashSet would keep. Mention this and you have separated yourself from candidates who memorized only the duplicate rule.

TreeSet's superpower: navigation and range queries

Paying O(log n) per operation buys you the NavigableSet API — queries no hash-based set can answer:

TreeSet<Integer> scores = new TreeSet<>(Set.of(35, 48, 62, 71, 89, 94));

System.out.println(scores.first());        // 35
System.out.println(scores.last());         // 94
System.out.println(scores.ceiling(63));    // 71  (smallest >= 63)
System.out.println(scores.floor(63));      // 62  (largest  <= 63)
System.out.println(scores.headSet(62));    // [35, 48]        (< 62)
System.out.println(scores.tailSet(71));    // [71, 89, 94]    (>= 71)

If your problem sounds like "find the nearest", "everything between X and Y", or "keep a sorted leaderboard", TreeSet answers in O(log n) where a HashSet would need a full O(n) scan plus a sort.

Set operations: union, intersection, difference

Sets model membership math directly, which is handy for tasks like comparing enrolled students against placed students:

Set<String> javaBatch = new HashSet<>(Set.of("Asha", "Ravi", "Meena", "Kiran"));
Set<String> sqlBatch  = new HashSet<>(Set.of("Ravi", "Kiran", "Divya"));

Set<String> union = new HashSet<>(javaBatch);
union.addAll(sqlBatch);            // everyone in either batch

Set<String> both = new HashSet<>(javaBatch);
both.retainAll(sqlBatch);          // intersection: [Ravi, Kiran]

Set<String> onlyJava = new HashSet<>(javaBatch);
onlyJava.removeAll(sqlBatch);      // difference: [Asha, Meena]

Each of these is O(n) in the size of the operand set — dramatically better than the nested-loop O(n²) approach with two Lists.

Pro tip: Copy before you mutate. retainAll and removeAll modify the set they are called on, so wrap the original in new HashSet<>(original) first unless you genuinely want it changed.

Choosing the right Set

Ask two questions, in order:

1. Do I need sorted order or range queries? Yes → TreeSet. Accept O(log n) and make sure elements are Comparable (or supply a Comparator). No nulls.
2. Do I need iteration in insertion order? Yes → LinkedHashSet (tiny memory premium over HashSet). No → HashSet, the default, with O(1) average everything.

For immutable sets of constants, Set.of(...) (Java 9+) is compact, null-hostile and duplicate-hostile — passing a duplicate to it throws IllegalArgumentException at creation time, which is usually exactly the early failure you want.

Where Sets fit in your prep

Uniqueness problems, deduplication, visited-tracking in algorithms, and the equals/hashCode contract all funnel through Set questions — they appear constantly in Java collections interview rounds. Go deeper into the default implementation with HashSet: how it works, or zoom out to the full Collections Framework map. For a guided path through all of this with hands-on projects, check the Java Full Stack course.