Set

A Collection that enforces uniqueness — no duplicate elements — with HashSet, LinkedHashSet, and TreeSet offering hashing-based, insertion-ordered, and sorted variants.

Set is the Collections Framework interface modeling a mathematical set: a group of elements with no duplicates. Unlike List, it defines no positional index; unlike Map, it holds single elements, not key-value pairs. Its three common implementations — HashSet, LinkedHashSet, and TreeSet — differ mainly in what iteration order (if any) they guarantee and how they determine uniqueness.

What Is Set

java.util.Set<E> extends Collection<E> but adds the constraint that no two elements may be equal according to equals(): calling add() with an element that's already present (by equals()) is a no-op and add() returns false.

import java.util.*;

Set<String> tags = new HashSet<>();
System.out.println(tags.add("java"));  // true — added
System.out.println(tags.add("java"));  // false — duplicate, ignored
System.out.println(tags.size());        // 1

HashSet

HashSet is backed internally by a hash table (implemented, in practice, on top of a HashMap). It offers average O(1) add/remove/contains, but guarantees no particular iteration order — the order may appear to change as elements are added or the internal table resizes, and should never be relied upon.

Set<Integer> s = new HashSet<>();
s.add(3); s.add(1); s.add(2);
System.out.println(s); // iteration order not guaranteed; commonly NOT [3, 1, 2]

LinkedHashSet

LinkedHashSet extends HashSet and additionally maintains a doubly linked list running through its entries, so iteration order matches insertion order — predictable, at a small extra memory and bookkeeping cost compared to plain HashSet.

Set<Integer> s = new LinkedHashSet<>();
s.add(3); s.add(1); s.add(2);
System.out.println(s); // [3, 1, 2] — insertion order preserved

TreeSet

TreeSet implements SortedSet (and NavigableSet), backed by a red-black tree, keeping elements in sorted order at all times — either their natural order (via Comparable) or an explicit Comparator supplied at construction. add/remove/contains are O(log n), slower than HashSet's average O(1) but with the benefit of always-sorted iteration and range operations (first(), last(), headSet(), tailSet()).

Set<Integer> s = new TreeSet<>();
s.add(3); s.add(1); s.add(2);
System.out.println(s);                 // [1, 2, 3] — always sorted

TreeSet<Integer> ts = (TreeSet<Integer>) s;
System.out.println(ts.first());        // 1
System.out.println(ts.last());         // 3
System.out.println(ts.headSet(3));      // [1, 2] — elements less than 3

Uniqueness: The equals()/hashCode() Contract

For hash-based sets (HashSet, LinkedHashSet), uniqueness and correct lookup depend on the element class correctly overriding both equals() and hashCode(), consistently. If equals() is overridden but hashCode() is not (or the two are inconsistent), objects considered equal can be placed in different hash buckets and end up as separate 'duplicate' entries or fail to be found by contains(). For TreeSet, uniqueness and ordering are instead determined by compareTo() (or the supplied Comparator) — two elements that compare as 0 are treated as duplicates, even if equals() would say otherwise.

class Point {
    int x, y;
    Point(int x, int y) { this.x = x; this.y = y; }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Point p)) return false;
        return x == p.x && y == p.y;
    }
    @Override
    public int hashCode() {
        return Objects.hash(x, y); // must be consistent with equals()
    }
}

Ordering: Hashing versus Sorting

This is a common exam-style distinction: hashing gives fast unordered (or insertion-ordered) access; sorting gives slower but always-ordered access with useful range queries. Choose based on whether you need order at all, and if so, which kind.

Implementation    Iteration order          Underlying structure
HashSet           unspecified              hash table
LinkedHashSet      insertion order          hash table + linked list
TreeSet            sorted order             red-black tree (self-balancing BST)

Uniqueness basis:
HashSet / LinkedHashSet -> equals() + hashCode()
TreeSet                  -> compareTo() / Comparator (compareTo()==0 means "same")

Basic Syntax and Common Operations

Set<String> a = new HashSet<>(Set.of("x", "y", "z"));
Set<String> b = new HashSet<>(Set.of("y", "z", "w"));

Set<String> union = new HashSet<>(a);
union.addAll(b);                     // union: {x, y, z, w}

Set<String> intersection = new HashSet<>(a);
intersection.retainAll(b);           // intersection: {y, z}

Set<String> difference = new HashSet<>(a);
difference.removeAll(b);             // difference: {x}

Practical Usage

Sets are the natural choice whenever 'is this already present?' or 'give me the distinct items' matters more than order or position — deduplicating a list, tracking visited nodes in a graph traversal, representing a collection of unique tags or permissions, or computing set algebra (union/intersection/difference) between groups.

List<String> withDuplicates = List.of("a", "b", "a", "c", "b");
Set<String> unique = new LinkedHashSet<>(withDuplicates); // dedupe, keep first-seen order
System.out.println(unique); // [a, b, c]

Edge Cases

HashSet permits one null element; TreeSet does not permit null (attempting to add null throws NullPointerException, since it can't be compared against existing elements) unless a Comparator explicitly handles null, which is unusual.

Mutating an object already stored in a HashSet or TreeSet, in a way that changes its hashCode() or its comparison order, corrupts the set's internal structure — the element may become unfindable via contains()/remove() even though it's still physically present in the underlying structure. Avoid using mutable fields that affect equals()/hashCode()/compareTo() as set elements once inserted.

Set.of(...) is immutable, rejects null, and also throws IllegalArgumentException if you pass duplicate elements to the factory method itself.

Complete Example

import java.util.*;

public class TagManager {
    public static void main(String[] args) {
        Set<String> articleTags = new TreeSet<>();
        articleTags.add("java");
        articleTags.add("collections");
        articleTags.add("java"); // duplicate — ignored
        articleTags.add("beginner");

        System.out.println("Tags (sorted): " + articleTags);
        System.out.println("Has 'java'? " + articleTags.contains("java"));

        Set<String> newTags = new HashSet<>(Set.of("advanced", "java"));
        Set<String> onlyNew = new TreeSet<>(newTags);
        onlyNew.removeAll(articleTags);
        System.out.println("Truly new tags: " + onlyNew); // [advanced]
    }
}

Mental Model

Think of a HashSet as a huge wall of unlabeled cubbyholes, sorted only by a computed number (the hash) — fast to check if something's already there, but the cubbyholes aren't in any meaningful reading order. A LinkedHashSet is the same wall with a string threaded through the cubbyholes in the order you filled them, so you can walk that string to read them back in order. A TreeSet is a sorted filing cabinet — slower to file each new document because it has to find the exact alphabetical slot, but always readable start-to-finish in order.

Quick Reference

Set<E> — no duplicates, no positional index

HashSet<E>       — O(1) avg, no order guarantee, one null allowed
LinkedHashSet<E> — O(1) avg, insertion order, one null allowed
TreeSet<E>       — O(log n), sorted order, no null (NPE)

Set operations:
  union:        a.addAll(b)
  intersection: a.retainAll(b)
  difference:   a.removeAll(b)

Uniqueness: equals()+hashCode() for hash-based sets;
            compareTo()/Comparator for TreeSet

Key Takeaways

Set forbids duplicate elements (by equals(), or by compareTo() for TreeSet); add() on an existing element is a no-op returning false.

HashSet gives average O(1) operations with no order guarantee; LinkedHashSet adds predictable insertion-order iteration; TreeSet gives always-sorted O(log n) operations.

Hash-based sets require correctly implemented, consistent equals() and hashCode() on stored elements; TreeSet relies on compareTo() or a supplied Comparator instead.

addAll/retainAll/removeAll implement union/intersection/difference set algebra.

Mutating an element's fields that affect its hash or comparison after inserting it into a set corrupts the set's internal structure.

class Point { int x, y; @Override public boolean equals(Object o) { /* compares x,y */ return true; } // hashCode() not overridden — inherits Object's identity hash } Set<Point> pts = new HashSet<>(); pts.add(new Point(1, 1)); pts.add(new Point(1, 1)); // treated as a DIFFERENT element — added anyway class Point { int x, y; @Override public boolean equals(Object o) { /* compares x,y */ return true; } @Override public int hashCode() { return Objects.hash(x, y); } }

Overriding equals() without a consistent hashCode() breaks HashSet's ability to recognize duplicates, since it uses hashCode() first to locate the bucket to check.

TreeSet<String> ts = new TreeSet<>(); ts.add(null); // throws NullPointerException

TreeSet<String> ts = new TreeSet<>(); // simply don't add null to a TreeSet — it has no natural way to compare it

TreeSet cannot accept null elements (with a natural ordering) because it needs to compare every element to place it in sorted order, and null has no defined comparison.

Set<Point> visited = new HashSet<>(); Point p = new Point(1, 1); visited.add(p); p.x = 99; // mutate a field used in hashCode()/equals() after insertion visited.contains(new Point(1, 1)); // may now return false unexpectedly

// Prefer immutable elements in hash-based sets, or never mutate // fields that affect equals()/hashCode() after insertion.

Mutating a field that affects hashCode() after an object is stored in a HashSet moves it out of the bucket the set expects it in, silently corrupting lookups.

What happens when you call add() on a Set with an element that's already present?

The call is a no-op — the set is unchanged, and add() returns false rather than throwing or inserting a duplicate.

Which Set implementation guarantees iteration order matches insertion order, and how does it achieve this?

LinkedHashSet, by maintaining an additional doubly linked list through its hash-table entries in insertion order, alongside the underlying hash table used for fast lookups.

Why must hashCode() be overridden consistently with equals() for correct behavior in a HashSet?

HashSet uses an element's hashCode() to determine which internal bucket to search first; if two equal objects have different hash codes, the set may fail to recognize them as duplicates or fail to find an existing element via contains().

What determines uniqueness in a TreeSet, and how can that differ from equals()-based uniqueness?

compareTo() (or a supplied Comparator) determines uniqueness in a TreeSet — two elements that compare as 0 are treated as the same element for set purposes, even if their equals() method would consider them different.

How do you compute the union, intersection, and difference of two Sets using standard Collection methods?

Union via addAll(), intersection via retainAll(), and difference via removeAll(), typically applied to a copy of one of the sets so the originals aren't mutated.

Interview: Why does TreeSet throw NullPointerException when adding null, while HashSet allows one null element?

TreeSet must determine sorted position via compareTo() or a Comparator, and comparing null to another element has no defined meaning, so it throws; HashSet uses hashing and equals() for placement, and null can be handled as a special case (Objects.hashCode(null) is 0, and equals-based lookup can special-case null), so it's permitted.

Write a method that returns true if a List<String> contains any duplicate elements, using a Set.

static boolean hasDuplicates(List<String> list) { Set<String> seen = new HashSet<>(); for (String s : list) { if (!seen.add(s)) { return true; // add() returned false => s was already present } } return false; }

Set.add() returning false is a convenient signal that the element was already present, letting this run in a single pass without a separate contains() check.

What does this print?

[3, 4] — retainAll keeps only the elements also present in b (intersection), and TreeSet keeps the result sorted.

Write a program that reads a list of email addresses (some duplicated, case-sensitive) and prints only the distinct ones in the order they first appeared, using a LinkedHashSet.

import java.util.*; public class DistinctEmails { public static void main(String[] args) { List<String> emails = List.of( "a@x.com", "b@x.com", "a@x.com", "c@x.com", "b@x.com"); Set<String> distinct = new LinkedHashSet<>(emails); for (String email : distinct) { System.out.println(email); } } }

Constructing a LinkedHashSet from the list both deduplicates and preserves first-occurrence order, printing a@x.com, b@x.com, c@x.com in that order.

Set<Integer> a = new TreeSet<>(Set.of(1, 2, 3, 4));
Set<Integer> b = new TreeSet<>(Set.of(3, 4, 5, 6));
a.retainAll(b);
System.out.println(a);