Java Set Interface — Collections Without Duplicates

A Set is a collection that contains no duplicate elements. It models the mathematical set abstraction — you either have an element or you don’t.

---

The Set Contract

1. No duplicates — adding an existing element has no effect.
2. At most one null element (implementation-dependent).
3. No guaranteed order (unless using LinkedHashSet or TreeSet).

Set<String> colors = new HashSet<>();
colors.add("Red");
colors.add("Blue");
colors.add("Red");      // duplicate — ignored
System.out.println(colors.size());  // 2

---

Set Implementations

Implementation	Order	Null	Add/Contains/Remove	Backed By
HashSet	None	✅ (one)	O(1) average	HashMap
LinkedHashSet	Insertion order	✅ (one)	O(1) average	LinkedHashMap
TreeSet	Sorted (natural/comparator)	❌	O(log n)	TreeMap
EnumSet	Enum declaration order	❌	O(1)	Bit vector

---

HashSet

The default Set implementation — backed by a HashMap internally:

Set<String> tags = new HashSet<>();
tags.add("java");
tags.add("tutorial");
tags.add("collections");

tags.contains("java");  // true — O(1)
tags.remove("tutorial"); // true — O(1)

How HashSet Determines Uniqueness

Two objects are considered equal if:

1. a.equals(b) returns true, AND
2. a.hashCode() == b.hashCode()

public class Product {
    private String id;
    private String name;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Product p)) return false;
        return Objects.equals(id, p.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

Set<Product> products = new HashSet<>();
products.add(new Product("P1", "Widget"));
products.add(new Product("P1", "Gadget"));  // same ID → duplicate
System.out.println(products.size());  // 1

Always override both equals() and hashCode() together. Violating this contract causes silent bugs in HashSet and HashMap.

---

LinkedHashSet

Maintains insertion order while still providing O(1) operations:

Set<String> steps = new LinkedHashSet<>();
steps.add("Login");
steps.add("Browse");
steps.add("Checkout");
steps.add("Pay");

System.out.println(steps);
// [Login, Browse, Checkout, Pay] — insertion order preserved

Use when you need uniqueness + predictable iteration order.

---

TreeSet

A sorted set backed by a Red-Black tree:

Set<Integer> numbers = new TreeSet<>();
numbers.add(42);
numbers.add(7);
numbers.add(99);
numbers.add(23);

System.out.println(numbers);  // [7, 23, 42, 99] — sorted

NavigableSet Methods

TreeSet<Integer> set = new TreeSet<>(List.of(10, 20, 30, 40, 50));

set.first();        // 10
set.last();         // 50
set.lower(30);      // 20 — strictly less than
set.higher(30);     // 40 — strictly greater than
set.floor(25);      // 20 — less than or equal
set.ceiling(25);    // 30 — greater than or equal
set.headSet(30);    // [10, 20] — elements < 30
set.tailSet(30);    // [30, 40, 50] — elements >= 30
set.subSet(20, 40); // [20, 30] — from 20 (inclusive) to 40 (exclusive)

Custom Ordering

Set<String> names = new TreeSet<>(Comparator.comparing(String::length));
names.add("Bob");
names.add("Alice");
names.add("Jo");
System.out.println(names);  // [Jo, Bob, Alice] — sorted by length

TreeSet uses compareTo() (or Comparator) for equality — not equals(). Two elements are “equal” if compareTo() returns 0.

---

Immutable Sets (Java 9+)

Set<String> immutable = Set.of("A", "B", "C");
// immutable.add("D");  // UnsupportedOperationException

Set<String> copy = Set.copyOf(mutableSet);  // Java 10+

Set.of() does not allow nulls and does not allow duplicates (throws IllegalArgumentException).

---

Set Operations

Set<String> a = new HashSet<>(Set.of("A", "B", "C"));
Set<String> b = Set.of("B", "C", "D");

// Union
Set<String> union = new HashSet<>(a);
union.addAll(b);              // [A, B, C, D]

// Intersection
Set<String> intersection = new HashSet<>(a);
intersection.retainAll(b);    // [B, C]

// Difference
Set<String> difference = new HashSet<>(a);
difference.removeAll(b);      // [A]

// Symmetric difference
Set<String> symDiff = new HashSet<>(a);
symDiff.addAll(b);
Set<String> common = new HashSet<>(a);
common.retainAll(b);
symDiff.removeAll(common);    // [A, D]

---

Choosing the Right Set

Need fastest add/contains/remove?
└── HashSet (O(1), no order)

Need insertion order?
└── LinkedHashSet (O(1), ordered)

Need sorted elements?
└── TreeSet (O(log n), sorted)

Working with enums?
└── EnumSet (most efficient for enum types)

---

Common Mistakes

Mistake	Problem	Fix
Not overriding hashCode()	HashSet treats equal objects as different	Override both equals() and hashCode()
Using mutable objects as set elements	Element’s hash changes → “lost” in set	Use immutable keys or don’t mutate after adding
Expecting order from HashSet	No guaranteed order	Use LinkedHashSet or TreeSet
null in TreeSet	NullPointerException	TreeSet can’t compare null

---

Key Takeaways

1. Set = no duplicates, uniqueness determined by equals() + hashCode().
2. HashSet — O(1), no order. Default choice.
3. LinkedHashSet — O(1), insertion order preserved.
4. TreeSet — O(log n), sorted. Use for range queries.
5. Always override both equals() and hashCode() for custom objects in sets.
6. Use Set.of() for small immutable sets.

---

What’s Next?

Next: Map Interface — key-value pairs, iteration, and the rich Map API.