The Project | About Us | Contribute | Donations | License

HOME

In the previous lesson you took HashMap apart piece by piece: the hash function, the buckets, the collisions, the load factor, the rehash and —finally— the exact reason why equals and hashCode always have to go together. That investment is about to pay immediate interest, because a HashSet is literally a HashMap with dummy values. It is not a teaching metaphor: it is its real implementation, and you will see it in the JDK's source code.

A set (Set) models the mathematical idea of a set: a collection with no repeated elements. That single restriction on its own solves a whole family of problems that with lists require loops and checks: detecting duplicates, checking membership, crossing two collections to find out what they have in common or how they differ. In BiblioTech you already used a Set<String> as a stopgap to avoid repeating ISBNs; by the end of this lesson it will be a piece of design with all its potential unfolded.

You will also see the most spectacular performance difference in the whole module: searching in a Set versus searching in a List. It is not 20% better. It is five orders of magnitude.

What a set is
The Set interface and its API
HashSet is a HashMap in disguise
add returns a boolean, and that changes everything
Set operations
HashSet, LinkedHashSet and TreeSet
TreeSet, SortedSet and NavigableSet
The danger of mutating a stored element
Immutable sets
contains on a Set versus a List
Applying it to BiblioTech
Common Mistakes and Tips
Exercises

What a set is

A Set is a collection with two defining properties:

It allows no duplicates. Adding an element that is already there does nothing.
It guarantees no order (in the case of HashSet). The traversal order is unpredictable and can change.

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

Set<String> cataloguedIsbns = new HashSet<>();

cataloguedIsbns.add("978-0000000001");
cataloguedIsbns.add("978-0000000002");
cataloguedIsbns.add("978-0000000001");    // already there: ignored

System.out.println(cataloguedIsbns.size());     // 2, not 3
System.out.println(cataloguedIsbns);            // unpredictable order

What exactly does "already there" mean? This is where 03-09 and 05-05 come together: two elements are the same if equals says they are, and to get as far as comparing them the set uses hashCode. Everything you learned about map keys applies exactly the same to set elements.

The question that decides between List and Set:

Question	Answer	Collection
Can there be repeated elements, and does each one count?	Yes	`List`
Is a repeat an error or redundant data?	Yes	`Set`
Do order and position matter?	Yes	`List`
Do I only care about "is it there or not"?	Yes	`Set`

Clear examples in BiblioTech:

The catalogue is a List: there could be two copies of the same book and the display order matters.
The catalogued ISBNs are a Set: a repeated ISBN is a registration error.
The employees with overdue loans are a Set: an employee with three overdue loans appears once.
The notices already sent are a Set: we do not want to send the same one twice.

When you choose Set, uniqueness stops being something you have to police and becomes guaranteed by the structure. That is design: the type documents and enforces the rule.

The `Set` interface and its API

Set extends Collection and, curiously, adds not a single new method. What changes is the contract: add can reject, and there is no access by index.

Method	What it does	Complexity on a `HashSet`
`add(E e)`	Adds if absent. Returns `false` if it was already there	O(1)
`remove(Object o)`	Removes. Returns `true` if there was something	O(1)
`contains(Object o)`	Is it there?	O(1)
`size()` / `isEmpty()`	How many there are	O(1)
`clear()`	Empties it	O(n)
`addAll(Collection c)`	Union with another collection	O(m)
`retainAll(Collection c)`	Intersection	O(n)
`removeAll(Collection c)`	Difference	O(m)
`containsAll(Collection c)`	Is it a superset?	O(m)
`removeIf(Predicate)`	Removes those matching	O(n)
`forEach(Consumer)`	Traverses	O(n)
`iterator()`	Explicit traversal	O(n)
`toArray(T[] a)`	Dumps into an array	O(n)

What there is not, and it is important to notice:

There is no get(i). A set has no positions. To reach a specific element, either you traverse it, or you ask whether it is there with contains.
There is no set(i, e) and no indexOf.
There is no order in a HashSet. If you need order, you change implementation.

Basic usage:

Set<String> noticedEmployees = new HashSet<>();
noticedEmployees.add("EMP-001");
noticedEmployees.add("EMP-002");

if (noticedEmployees.contains("EMP-001")) {           // O(1)
    System.out.println("Marta has already been noticed");
}

noticedEmployees.remove("EMP-002");
System.out.println(noticedEmployees.size());           // 1

for (String id : noticedEmployees) {                   // for-each: the only way to traverse
    System.out.println(id);
}

`HashSet` is a `HashMap` in disguise

Open java.util.HashSet in the JDK and you will find this:

public class HashSet<E> extends AbstractSet<E> implements Set<E> {

    private transient HashMap<E, Object> map;          // a HashMap inside

    // The dummy value associated with ALL the keys
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;    // put returns null if the key was new
    }

    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }

    public int size() {
        return map.size();
    }

    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }
}

A HashSet is a HashMap in which only the keys matter. The set's elements are the map's keys; every value is the same sentinel object PRESENT, which means nothing and only exists because HashMap needs something to store.

flowchart LR
    subgraph HS["HashSet"]
        M["map →"]
    end
    subgraph HM["internal HashMap"]
        E1["'978-0000000001' → PRESENT"]
        E2["'978-0000000002' → PRESENT"]
        E3["'REV-2024-03' → PRESENT"]
    end
    M --> HM
    P["PRESENT<br/>(a single shared object)"]
    E1 -.-> P
    E2 -.-> P
    E3 -.-> P

From this identity follows everything you need to know about HashSet, without learning anything new:

Property of `HashSet`	Because the internal `HashMap`...
`add`, `contains`, `remove` are O(1)	...locates the bucket by computing the hash
It allows no duplicates	...allows no duplicate keys
It guarantees no order	...guarantees no key order
It allows a single `null`	...allows a single `null` key
It requires correct `equals` and `hashCode`	...requires them of its keys
Elements must be immutable	...its keys must be
It has a load factor and a rehash	...it has them
A bucket with 8+ elements becomes a tree	...it does

And from there comes this lesson's central warning: everything that broke a HashMap in 05-05 breaks a HashSet in exactly the same way. An element with equals but without hashCode enters the set and is never found, and two "duplicates" can be put into a set that guarantees uniqueness:

// BrokenKey had equals but NOT hashCode (05-05)
Set<BrokenKey> set = new HashSet<>();
set.add(new BrokenKey("978-0000000001"));
set.add(new BrokenKey("978-0000000001"));    // "equal", but with a different hash

System.out.println(set.size());              // 2   <-- DUPLICATES in a Set
System.out.println(set.contains(new BrokenKey("978-0000000001")));   // false

The same explanation as in 05-05: contains computes the hash, goes to a bucket that is empty and returns false without ever calling equals.

A HashSet also has capacity constructors, with the same semantics and the same arithmetic as a HashMap:

Set<String> isbn = new HashSet<>();                                  // default
Set<String> large = new HashSet<>((int)(50_000 / 0.75f) + 1);        // no rehashes
Set<Material> copy = new HashSet<>(materialList);                    // from another collection

That last constructor is a very useful idiom: removing duplicates from a list in one line.

List<String> withDuplicates = List.of("A", "B", "A", "C", "B");
Set<String> withoutDuplicates = new HashSet<>(withDuplicates);      // [A, B, C], unpredictable order

// And if you want a list with no duplicates preserving the original order:
List<String> list = new ArrayList<>(new LinkedHashSet<>(withDuplicates));   // [A, B, C]

`add` returns a `boolean`, and that changes everything

Collection.add returns a boolean. On a List that value is always true and nobody looks at it. On a Set it is valuable information:

add returns true if the element was added (it was new) and false if it was already there.

That solves the "detect duplicates" problem with no prior check at all:

// WITHOUT exploiting it: two operations, two lookups
if (cataloguedIsbns.contains(isbn)) {
    System.out.println("WARNING: duplicate ISBN");
} else {
    cataloguedIsbns.add(isbn);
}

// EXPLOITING it: one operation, one lookup
if (!cataloguedIsbns.add(isbn)) {
    System.out.println("WARNING: duplicate ISBN -> " + isbn);
}

The second version is not only shorter: it does half the work, because contains followed by add walks the same bucket twice.

Typical applications of the pattern:

// 1. Process each element ONLY the first time it appears
Set<String> alreadyProcessed = new HashSet<>();
for (Loan l : loans) {
    if (alreadyProcessed.add(l.getEmployee().getIdentifier())) {
        sendMonthlySummary(l.getEmployee());         // only once per employee
    }
}

// 2. Detect the first duplicate in a list
Set<String> seen = new HashSet<>();
for (String isbn : isbnsFromFile) {
    if (!seen.add(isbn)) {
        System.out.println("First repeat: " + isbn);
        break;
    }
}

// 3. Count how many distinct elements there are
Set<String> distinct = new HashSet<>(allIsbns);
System.out.println("Distinct materials: " + distinct.size());

// 4. Avoid infinite cycles when walking relationships
Set<Material> visited = new HashSet<>();
// ... if (!visited.add(current)) { return; }  // we have already been here

The sibling methods follow the same logic:

Method	Returns `true` when...
`add(e)`	The element was not there and was added
`remove(o)`	The element was there and was removed
`addAll(c)`	At least one of the elements was new
`removeAll(c)`	At least one was removed
`retainAll(c)`	The set changed

Set operations

Here Set shows that it is not a crippled List, but a structure with an algebra of its own. The four classic operations from set theory each have their method:

Set<String> withLoan    = new HashSet<>(Set.of("EMP-001", "EMP-002", "EMP-003"));
Set<String> withOverdue = new HashSet<>(Set.of("EMP-002", "EMP-003", "EMP-005"));

flowchart TB
    subgraph diagram["Employees"]
        A["withLoan<br/>EMP-001, EMP-002, EMP-003"]
        B["withOverdue<br/>EMP-002, EMP-003, EMP-005"]
        I["INTERSECTION<br/>EMP-002, EMP-003<br/>(with a loan AND overdue)"]
        A --- I
        B --- I
    end

Union: `addAll`

All the elements of both sets, without repeating.

Set<String> union = new HashSet<>(withLoan);      // a copy, so as not to destroy the original
union.addAll(withOverdue);
System.out.println(union);      // [EMP-001, EMP-002, EMP-003, EMP-005]

Intersection: `retainAll`

Only those in both.

Set<String> intersection = new HashSet<>(withLoan);
intersection.retainAll(withOverdue);
System.out.println(intersection);   // [EMP-002, EMP-003]

Difference: `removeAll`

Those in the first but not in the second.

Set<String> onlyWithLoan = new HashSet<>(withLoan);
onlyWithLoan.removeAll(withOverdue);
System.out.println(onlyWithLoan);       // [EMP-001]

// Careful: the difference is NOT symmetric
Set<String> onlyWithOverdue = new HashSet<>(withOverdue);
onlyWithOverdue.removeAll(withLoan);
System.out.println(onlyWithOverdue);    // [EMP-005]

Subset: `containsAll`

Are all of the second's elements in the first?

Set<String> some = Set.of("EMP-002", "EMP-003");
System.out.println(withLoan.containsAll(some));         // true: it is a subset
System.out.println(withLoan.containsAll(withOverdue));  // false: EMP-005 is missing

Symmetric difference

It has no method of its own, but it is composed from the previous ones: those in one or the other, but not in both.

Set<String> symmetric = new HashSet<>(withLoan);
symmetric.addAll(withOverdue);                        // union

Set<String> common = new HashSet<>(withLoan);
common.retainAll(withOverdue);                        // intersection

symmetric.removeAll(common);                          // union minus intersection
System.out.println(symmetric);      // [EMP-001, EMP-005]

Summary table

Mathematical operation	Method	Effect
Union (A ∪ B)	`a.addAll(b)`	A ends up containing everything
Intersection (A ∩ B)	`a.retainAll(b)`	A keeps only what is common
Difference (A − B)	`a.removeAll(b)`	A loses what was in B
Subset (B ⊆ A)	`a.containsAll(b)`	Modifies nothing, just queries
Disjoint (A ∩ B = ∅)	`Collections.disjoint(a, b)`	`true` if they share nothing

Critical warning: the first three modify the set they are invoked on. If you need to keep the originals —which is nearly always—, work on a copy:

Set<String> result = new HashSet<>(original);      // a COPY
result.retainAll(other);                           // the copy is modified

Forgetting the copy and destroying the original set is one of the most frequent mistakes with set operations.

`HashSet`, `LinkedHashSet` and `TreeSet`

Aspect	`HashSet`	`LinkedHashSet`	`TreeSet`
Internal structure	`HashMap`	`LinkedHashMap`	`TreeMap` (red-black tree)
Traversal order	None guaranteed	Insertion	Sorted
`add` / `contains` / `remove`	O(1)	O(1)	O(log n)
Memory	Lower	+2 references per element	Higher
`null` allowed	One	One	No: `NullPointerException`
Element requirement	`equals` + `hashCode`	`equals` + `hashCode`	`Comparable` or `Comparator`
Range operations	No	No	Yes: `headSet`, `ceiling`...
When to use it	By default	Reproducible order	Permanent ordering, ranges

The three in action on the same data:

List<String> input = List.of("Magazine", "Book", "DVD", "Book", "Audiobook");

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

System.out.println("HashSet:       " + hash);     // [DVD, Magazine, Book, Audiobook] (unpredictable)
System.out.println("LinkedHashSet: " + linked);   // [Magazine, Book, DVD, Audiobook]  (insertion)
System.out.println("TreeSet:       " + tree);     // [Audiobook, Book, DVD, Magazine]  (alphabetical)

All three have 4 elements: the repeated "Book" was discarded in all three cases.

When to use each one:

HashSet: by default. If all you care about is "is it there or not", it is the answer.
LinkedHashSet: when the output has to be reproducible —reports, tests, generated files— or when you want to remove duplicates preserving the original order. The overhead is minimal.
TreeSet: when you need to traverse in order every time, or to query ranges and neighbours. Remember you go from O(1) to O(log n): with a million elements that is about 20 comparisons per operation, generally acceptable.

`TreeSet`, `SortedSet` and `NavigableSet`

TreeSet implements NavigableSet, which extends SortedSet, which extends Set. Each level adds operations that only make sense if there is an order.

TreeSet<String> references = new TreeSet<>(Set.of(
    "978-0000000001", "978-0000000002", "978-0000000003", "DVD-0007", "REV-2024-03"));

// SortedSet: ends and ranges
System.out.println(references.first());        // 978-0000000001
System.out.println(references.last());         // REV-2024-03
System.out.println(references.headSet("DVD-0007"));    // the STRICTLY smaller ones
System.out.println(references.tailSet("DVD-0007"));    // the greater OR EQUAL ones
System.out.println(references.subSet("978-0000000002", "DVD-0007"));

// NavigableSet: neighbours
System.out.println(references.ceiling("978-0000000002x"));   // the smallest >= the given one
System.out.println(references.floor("978-0000000002x"));     // the greatest <= the given one
System.out.println(references.higher("978-0000000002"));     // strictly greater
System.out.println(references.lower("978-0000000002"));      // strictly smaller

// NavigableSet: extracting the ends (useful as a priority queue)
System.out.println(references.pollFirst());    // returns AND REMOVES the first
System.out.println(references.pollLast());     // returns AND REMOVES the last

// Reverse traversal
System.out.println(references.descendingSet());

Method	Returns
`first()` / `last()`	The smallest / greatest. `NoSuchElementException` if empty
`pollFirst()` / `pollLast()`	The smallest / greatest, removing it. `null` if empty
`headSet(e)`	A view of those smaller than `e`
`tailSet(e)`	A view of those greater than or equal to `e`
`subSet(a, b)`	A view of the range [a, b)
`ceiling(e)`	The smallest element ≥ e, or `null`
`floor(e)`	The greatest element ≤ e, or `null`
`higher(e)` / `lower(e)`	Strictly greater / smaller, or `null`
`descendingSet()`	A view in reverse order

The range views are live: removing from a headSet removes from the original TreeSet.

Natural order or `Comparator`

A TreeSet needs to know how to compare its elements. Two options:

// 1. Natural order: the elements implement Comparable
TreeSet<Card> byTitle = new TreeSet<>();             // Card implements Comparable (04-07)
byTitle.add(new Card("Refactoring",     "Martin Fowler", 1999));
byTitle.add(new Card("Effective Java",  "Joshua Bloch",  2018));
byTitle.add(new Card("Design Patterns", "Erich Gamma",   1994));
// traversal: Design Patterns, Effective Java, Refactoring

// 2. An explicit Comparator, picking up 04-06
TreeSet<Material> byRate = new TreeSet<>(
    Comparator.comparingDouble(Material::getDailyRate)
              .thenComparing(Material::getReference));    // tie-breaker: MANDATORY

If the element does not implement Comparable and you do not give it a Comparator, the first insertion throws ClassCastException.

And here there is a trap that has to be well understood. In a TreeSet, uniqueness is not decided by equals: it is decided by the comparator. Two elements are "the same one" if compareTo (or compare) returns 0.

TreeSet<Material> byRate = new TreeSet<>(
    Comparator.comparingDouble(Material::getDailyRate));   // NO tie-breaker

byRate.add(new Book("Effective Java",  "Joshua Bloch", "978-0000000001", 2018));  // 0.25
byRate.add(new Book("Design Patterns", "Erich Gamma",  "978-0000000002", 1994));  // 0.25

System.out.println(byRate.size());      // 1  <-- the second one was discarded!

The two books are different objects, with different equals, but their rate is the same, so the comparator returns 0 and the TreeSet considers them duplicates. It is a source of silent data loss.

An indispensable rule: a TreeSet's Comparator must be "total", that is, it must return 0 only for genuinely equal elements. Always add a unique tie-breaking criterion:

Comparator.comparingDouble(Material::getDailyRate)
          .thenComparing(Material::getReference)   // the reference is unique

This property is called consistency with equals, and in 05-09 you will study it as part of the Comparable contract.

The danger of mutating a stored element

It is the same problem as the mutable keys of 05-05, and for the same reason: a HashSet's elements are the internal HashMap's keys.

package com.nexussoftware.bibliotech.domain;

/** A mutable tag. A poor candidate for a Set element. */
public class Tag {
    private String name;                    // not final: the problem

    public Tag(String name) { this.name = name; }
    public void setName(String name) { this.name = name; }

    @Override public boolean equals(Object o) {
        return (o instanceof Tag t) && name.equals(t.name);
    }
    @Override public int hashCode() { return name.hashCode(); }
    @Override public String toString() { return name; }
}

Tag t = new Tag("java");
Set<Tag> tags = new HashSet<>();
tags.add(t);

System.out.println(tags.contains(t));     // true

t.setName("programming");                 // we MUTATE an element ALREADY STORED

System.out.println(tags.contains(t));     // false  <-- lost
System.out.println(tags.size());          // 1      <-- still inside
System.out.println(tags);                 // [programming]
System.out.println(tags.remove(t));       // false  <-- it cannot even be taken out

tags.add(t);                              // the same object is added AGAIN
System.out.println(tags.size());          // 2      <-- the same object, twice

The element stayed in the old hash's bucket. contains computes the new hash, looks in another bucket and does not find it. And since it does not find it, add inserts it again: now the same object is in the set twice, something that is supposed to be impossible.

In a TreeSet the problem is equivalent but with the ordering: if you mutate the field it is sorted by, the element stays on a branch of the tree where the binary search is never going to look for it.

TreeSet<Tag> sorted = new TreeSet<>(Comparator.comparing(Tag::toString));
Tag z = new Tag("zzz");
sorted.add(new Tag("aaa"));
sorted.add(z);
z.setName("aab");                         // now it should be second... but it is not rehomed
System.out.println(sorted.contains(z));   // unpredictable

Rule: a Set's elements must be immutable, or at least the fields taking part in equals/hashCode (or in the comparator) must be.

If you need to change an element, the only correct way is to take it out, modify it and put it back in:

tags.remove(t);              // it is taken out while its hash is still the right one
t.setName("programming");    // now it can be mutated
tags.add(t);                 // it is reinserted into the correct bucket

Immutable sets

As you saw in 05-02, Set.of(...) creates an immutable set:

Set<String> lendableTypes = Set.of("Book", "Magazine", "DVD");

Its properties, with one important peculiarity:

Immutable: add, remove and clear throw UnsupportedOperationException.
It allows no null: NullPointerException on creation.
It rejects duplicates on construction with IllegalArgumentException:

Set<String> wrong = Set.of("Book", "Magazine", "Book");
// IllegalArgumentException: duplicate element: Book

That behaviour surprises many people, because a normal HashSet ignores duplicates silently. It is deliberate: in a hand-written literal, a duplicate is almost certainly a mistake of yours, and it is better for it to fire on construction than to be discovered later.

The traversal order is deliberately randomised between runs, so that nobody writes code that depends on it.

Immutable sets are ideal for constants:

public static final Set<String> LENDABLE_TYPES = Set.of("Book", "Magazine", "DVD");
public static final Set<String> FINAL_STATUSES = Set.of("RETURNED", "CANCELLED", "LOST");

if (LENDABLE_TYPES.contains(m.getType())) { ... }      // O(1), and nobody can alter the list

And Set.copyOf(collection) creates an immutable copy of any collection, discarding duplicates without complaint (unlike Set.of):

Set<String> snapshot = Set.copyOf(listWithPossibleDuplicates);     // no exception

`contains` on a `Set` versus a `List`

This is the most impressive comparison in the whole module, and it deserves numbers.

package com.nexussoftware.bibliotech.presentation;

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

public class SearchComparison {

    public static void main(String[] args) {
        final int N = 100_000;
        final int QUERIES = 10_000;

        List<String> list = new ArrayList<>(N);
        Set<String>  set  = new HashSet<>((int)(N / 0.75f) + 1);
        for (int i = 0; i < N; i++) {
            String ref = "978-" + String.format("%010d", i);
            list.add(ref);
            set.add(ref);
        }

        // Warm-up
        for (int i = 0; i < 100; i++) { list.contains("978-0000099999"); }

        long t1 = System.nanoTime();
        int foundInList = 0;
        for (int i = 0; i < QUERIES; i++) {
            if (list.contains("978-" + String.format("%010d", N - 1))) { foundInList++; }
        }
        long msList = (System.nanoTime() - t1) / 1_000_000;

        long t2 = System.nanoTime();
        int foundInSet = 0;
        for (int i = 0; i < QUERIES; i++) {
            if (set.contains("978-" + String.format("%010d", N - 1))) { foundInSet++; }
        }
        long msSet = (System.nanoTime() - t2) / 1_000_000;

        System.out.printf("List.contains  x%d: %6d ms  (%d found)%n",
                          QUERIES, msList, foundInList);
        System.out.printf("Set.contains   x%d: %6d ms  (%d found)%n",
                          QUERIES, msSet, foundInSet);
        System.out.printf("The Set is approximately %d times faster%n",
                          msSet == 0 ? msList : msList / Math.max(msSet, 1));
    }
}

A typical result:

List.contains  x10000:   4180 ms  (10000 found)
Set.contains   x10000:      1 ms  (10000 found)
The Set is approximately 4180 times faster

And in operations per second:

Size	`List.contains` (worst case)	`Set.contains`	Advantage
100	~100 comparisons	1 operation	100×
10,000	~10,000	1	10,000×
1,000,000	~1,000,000	1	1,000,000×

From this comes one of the most profitable and simplest optimisations there is. This pattern, which turns up constantly in real code, is O(n×m):

// SLOW: for each material, walk the whole list of references
List<String> bannedReferences = loadBanned();            // 10,000 elements
for (Material m : catalog) {                             // 10,000 materials
    if (bannedReferences.contains(m.getReference())) {     // O(n) every time
        reject(m);
    }
}
// Total: 100,000,000 comparisons

And this is how it looks with one line changed:

// FAST: O(n + m)
Set<String> banned = new HashSet<>(loadBanned());        // O(m) conversion, just once
for (Material m : catalog) {
    if (banned.contains(m.getReference())) {             // O(1) every time
        reject(m);
    }
}
// Total: 20,000 operations

Professional rule: if you are going to do contains on a collection more than a few times, convert it to a Set first. The cost of the conversion (O(m), once) pays for itself almost immediately.

Applying it to BiblioTech

Two applications that consolidate what you have learned.

A `Set<String>` of catalogued ISBNs

You already used it in 05-02, but now with all its logic:

package com.nexussoftware.bibliotech.service;

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import com.nexussoftware.bibliotech.domain.Material;

/** Control of duplicate registrations in the catalogue. */
public class DuplicateControl {

    private final Set<String> cataloguedReferences = new HashSet<>();
    private final Set<String> rejected = new LinkedHashSet<>();     // order of appearance

    /**
     * Tries to register. The boolean from add does all the work:
     * true if it was new, false if it was already there. A single lookup.
     */
    public boolean register(Material m) {
        if (m == null || m.getReference() == null) { return false; }
        if (cataloguedReferences.add(m.getReference())) {
            return true;                                  // registration accepted
        }
        rejected.add(m.getReference());                   // registration rejected: we note it
        return false;
    }

    public boolean isCatalogued(String reference) {
        return cataloguedReferences.contains(reference);      // O(1)
    }

    public boolean deregister(String reference) {
        return cataloguedReferences.remove(reference);
    }

    /** Which of the references received are NOT catalogued: difference. */
    public Set<String> unknown(Set<String> references) {
        Set<String> result = new HashSet<>(references);       // a COPY: we do not destroy the parameter
        result.removeAll(cataloguedReferences);
        return result;
    }

    /** Which ones ARE catalogued: intersection. */
    public Set<String> known(Set<String> references) {
        Set<String> result = new HashSet<>(references);
        result.retainAll(cataloguedReferences);
        return result;
    }

    /** Does the file received cover the whole catalogue? */
    public boolean coversWholeCatalogue(Set<String> references) {
        return references.containsAll(cataloguedReferences);
    }

    public Set<String> rejectedAttempts() { return Set.copyOf(rejected); }
    public int catalogued() { return cataloguedReferences.size(); }
}

Crossing sets: overdue versus noticed

Here set operations solve in three lines what with lists would be nested loops:

package com.nexussoftware.bibliotech.service;

import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
import java.util.Comparator;
import com.nexussoftware.bibliotech.domain.Employee;
import com.nexussoftware.bibliotech.domain.Loan;

/** Manages who has to be noticed about delays, without repeating notices. */
public class NoticeManager {

    private final Set<Employee> alreadyNoticed = new HashSet<>();

    /**
     * Employees with at least one overdue loan. An employee with three
     * overdue loans appears ONCE: that is exactly a Set.
     */
    public Set<Employee> withOverdue(List<Loan> loans, int currentDay) {
        Set<Employee> result = new HashSet<>();
        for (Loan l : loans) {
            if (!l.isReturned() && l.isOverdue(currentDay)) {
                result.add(l.getEmployee());        // the repeats are discarded by themselves
            }
        }
        return result;
    }

    /** DIFFERENCE: overdue minus already noticed = pending a notice. */
    public Set<Employee> pendingNotice(List<Loan> loans, int currentDay) {
        Set<Employee> pending = new HashSet<>(withOverdue(loans, currentDay));
        pending.removeAll(alreadyNoticed);
        return pending;
    }

    /** INTERSECTION: those noticed who still have delays = time to escalate. */
    public Set<Employee> repeatOffenders(List<Loan> loans, int currentDay) {
        Set<Employee> offenders = new HashSet<>(withOverdue(loans, currentDay));
        offenders.retainAll(alreadyNoticed);
        return offenders;
    }

    /** Reverse DIFFERENCE: those noticed who owe nothing now = their notice can be cleared. */
    public Set<Employee> cleared(List<Loan> loans, int currentDay) {
        Set<Employee> cleared = new HashSet<>(alreadyNoticed);
        cleared.removeAll(withOverdue(loans, currentDay));
        return cleared;
    }

    /** Sends notices only to those who have not received one. Returns how many it sent. */
    public int sendNotices(List<Loan> loans, int currentDay) {
        int sent = 0;
        for (Employee e : pendingNotice(loans, currentDay)) {
            System.out.printf("NOTICE to %-16s (%s): has overdue material%n",
                              e.getName(), e.getIdentifier());
            alreadyNoticed.add(e);
            sent++;
        }
        return sent;
    }

    /** Clears the notices of those who have already returned everything. */
    public int purgeCleared(List<Loan> loans, int currentDay) {
        Set<Employee> toClear = cleared(loans, currentDay);
        alreadyNoticed.removeAll(toClear);
        return toClear.size();
    }

    /** Those noticed, sorted by name: a TreeSet with a Comparator. */
    public Set<Employee> noticedSorted() {
        Set<Employee> sorted = new TreeSet<>(
            Comparator.comparing(Employee::getName)
                      .thenComparing(Employee::getIdentifier));   // a UNIQUE tie-breaker
        sorted.addAll(alreadyNoticed);
        return sorted;
    }
}

Usage:

Employee marta = new Employee("Marta Ruiz",   "EMP-001");
Employee diego = new Employee("Diego Alonso", "EMP-002");
Employee nuria = new Employee("Nuria Vidal",  "EMP-003");

List<Loan> loans = List.of(
    new Loan(new Book("Effective Java",  "Joshua Bloch",  "978-0000000001", 2018), marta, 100),
    new Loan(new Book("Refactoring",     "Martin Fowler", "978-0000000003", 1999), marta, 101),
    new Loan(new Book("Design Patterns", "Erich Gamma",   "978-0000000002", 1994), diego, 105),
    new Loan(new Magazine("Java Magazine", "REV-2024-03", 42, "Monthly"),          nuria, 140)
);

NoticeManager manager = new NoticeManager();

System.out.println("With overdue on day 130: " + manager.withOverdue(loans, 130).size());
System.out.println("Notices sent: " + manager.sendNotices(loans, 130));
System.out.println("Notices on a second pass: " + manager.sendNotices(loans, 130));
System.out.println("Repeat offenders: " + manager.repeatOffenders(loans, 135).size());
System.out.print("Noticed (sorted): ");
manager.noticedSorted().forEach(e -> System.out.print(e.getName() + "  "));

With overdue on day 130: 2
NOTICE to Marta Ruiz       (EMP-001): has overdue material
NOTICE to Diego Alonso     (EMP-002): has overdue material
Notices sent: 2
Notices on a second pass: 0
Repeat offenders: 2
Noticed (sorted): Diego Alonso  Marta Ruiz

Notice the second pass: zero notices, because the set difference already excludes whoever was noticed. With lists, that would require a nested loop per employee. And observe that Marta, with two overdue loans, receives one notice: the Set deduplicates on its own.

Common Mistakes and Tips

Putting objects without correct equals/hashCode into a Set. They go in and are never found, and the set accepts "duplicates". It is the same failure as in 05-05: hashCode picks the bucket, equals picks the element. If you override one, override the other, over the same fields.

Mutating an element already stored. It stays in the old hash's bucket: unreachable, impossible to remove and liable to be duplicated. Use immutable elements, or remove → modify → put back.

Forgetting to copy before retainAll or removeAll. These methods modify the set they are called on. new HashSet<>(original) before operating, whenever you want to keep the original.

Depending on a HashSet's order. There is none guaranteed and it can change between runs or on insertion. Use LinkedHashSet for insertion order or TreeSet for natural order.

Using a non-total Comparator in a TreeSet. If two different elements compare to 0, the second is silently discarded. Always add a unique tie-breaking criterion, such as the reference or the identifier.

Expecting TreeSet to use equals. It does not: it uses compareTo/compare. An element that is different according to equals can be "the same" to the tree, and vice versa.

Putting null into a TreeSet. NullPointerException: null cannot be compared. HashSet does allow one, but avoid it anyway.

Set.of(...) with duplicates. It throws IllegalArgumentException on construction. If you expect duplicates, use new HashSet<>(collection) or Set.copyOf(collection).

Using List.contains inside a loop. It is the most profitable performance mistake to fix in the whole module: convert the list to a Set once and you go from O(n×m) to O(n+m).

Tip: choose Set for semantics, not for speed. A Set<String> of ISBNs documents that ISBNs are unique better than any comment, and the compiler and the structure enforce it. The speed is a bonus.

Tip: new LinkedHashSet<>(list) removes duplicates preserving the order. And new ArrayList<>(new LinkedHashSet<>(list)) gives back a clean list, in order, in one line.

Exercises

Exercise 1: catalogue control with sets

Write CatalogAudit to take two sets of references —the internal catalogue's and those from a supplier's file— and produce a report with:

Set<String> onlyInCatalog(): those we have and the supplier does not list (candidates for removal).
Set<String> onlyInSupplier(): those the supplier lists and we do not have (candidates for addition).
Set<String> inBoth(): the matching ones.
boolean catalogComplete(): whether the catalogue covers everything the supplier has.
boolean unrelated(): whether they share no reference at all (use Collections.disjoint).
Set<String> symmetricDifference(): those in one or the other but not in both.
String report(): a formatted summary.

No method may modify the sets it receives.

Exercise 2: the three implementations and their traps

Write SetDemo with a main that demonstrates, printing and explaining:

That HashSet, LinkedHashSet and TreeSet give different orders with the same data.
That an element without a correct hashCode allows duplicates in a HashSet.
That mutating a stored element makes it unreachable and even duplicable.
That a non-total Comparator makes a TreeSet discard different elements.
That Set.of with duplicates throws IllegalArgumentException (comment it out, do not run it) while new HashSet<>(list) ignores them.
The time difference between List.contains and Set.contains with 100,000 elements.

Exercise 3: material tags

Extend BiblioTech with a tagging system. Write TagManager to maintain a Map<String, Set<String>> (material reference → set of tags) and an inverse Map<String, Set<String>> (tag → set of references):

void tag(String reference, String... tags): uses computeIfAbsent and keeps both maps consistent.
Set<String> tagsOf(String reference).
Set<String> materialsWith(String tag).
Set<String> materialsWithAll(String... tags): intersection.
Set<String> materialsWithAny(String... tags): union.
Set<String> allTags(), sorted alphabetically.
void untag(String reference, String tag), cleaning up any entries left empty.

Solutions

Solution 1

package com.nexussoftware.bibliotech.service;

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

/** Compares the internal catalogue with a supplier's listing. */
public class CatalogAudit {

    private final Set<String> catalog;
    private final Set<String> supplier;

    public CatalogAudit(Set<String> catalog, Set<String> supplier) {
        // Defensive copies (03-07): nobody can alter our data from outside,
        // and we do not alter theirs.
        this.catalog  = (catalog  == null) ? Set.of() : Set.copyOf(catalog);
        this.supplier = (supplier == null) ? Set.of() : Set.copyOf(supplier);
    }

    /** DIFFERENCE catalog - supplier. We work on a copy. */
    public Set<String> onlyInCatalog() {
        Set<String> result = new HashSet<>(catalog);
        result.removeAll(supplier);
        return result;
    }

    /** DIFFERENCE supplier - catalog. Careful: the difference is NOT symmetric. */
    public Set<String> onlyInSupplier() {
        Set<String> result = new HashSet<>(supplier);
        result.removeAll(catalog);
        return result;
    }

    /** INTERSECTION. */
    public Set<String> inBoth() {
        Set<String> result = new HashSet<>(catalog);
        result.retainAll(supplier);
        return result;
    }

    /** SUBSET: does the catalogue contain everything the supplier offers? */
    public boolean catalogComplete() {
        return catalog.containsAll(supplier);
    }

    /** DISJOINT: they share not a single reference. */
    public boolean unrelated() {
        return Collections.disjoint(catalog, supplier);
    }

    /** SYMMETRIC DIFFERENCE: union minus intersection. */
    public Set<String> symmetricDifference() {
        Set<String> union = new HashSet<>(catalog);
        union.addAll(supplier);
        union.removeAll(inBoth());
        return union;
    }

    public String report() {
        StringBuilder sb = new StringBuilder();
        sb.append("=== Catalogue audit ===\n");
        sb.append(String.format("Internal catalogue:   %d references%n", catalog.size()));
        sb.append(String.format("Supplier listing:     %d references%n", supplier.size()));
        // TreeSet only so that the report always comes out in the same order
        sb.append(String.format("Matching:             %s%n", new TreeSet<>(inBoth())));
        sb.append(String.format("Removal candidates:   %s%n", new TreeSet<>(onlyInCatalog())));
        sb.append(String.format("Addition candidates:  %s%n", new TreeSet<>(onlyInSupplier())));
        sb.append(String.format("Catalogue complete:   %s%n", catalogComplete() ? "yes" : "no"));
        sb.append(String.format("Unrelated:            %s%n", unrelated() ? "yes" : "no"));
        return sb.toString();
    }
}

A test:

Set<String> ours   = Set.of("978-0000000001", "978-0000000002", "DVD-0007");
Set<String> theirs = Set.of("978-0000000002", "978-0000000003", "REV-2024-03");

System.out.print(new CatalogAudit(ours, theirs).report());

=== Catalogue audit ===
Internal catalogue:   3 references
Supplier listing:     3 references
Matching:             [978-0000000002]
Removal candidates:   [978-0000000001, DVD-0007]
Addition candidates:  [978-0000000003, REV-2024-03]
Catalogue complete:   no
Unrelated:            no

Two design ideas that go beyond the exercise. The first: every method copies before operating, because removeAll and retainAll are destructive; forgetting that would destroy the catalogue on the first query. The second: the TreeSet in report() only serves to make the output reproducible; a HashSet would give the same content in arbitrary order, which makes it impossible to compare reports or write tests.

And notice how little there is to write. Without sets, onlyInCatalog would be a nested O(n×m) loop; here it is an O(m) call.

Solution 2

package com.nexussoftware.bibliotech.presentation;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Objects;
import java.util.Set;
import java.util.TreeSet;

public class SetDemo {

    // An element WITHOUT hashCode
    static class BrokenTag {
        final String name;
        BrokenTag(String n) { this.name = n; }
        @Override public boolean equals(Object o) {
            return (o instanceof BrokenTag t) && Objects.equals(name, t.name);
        }
        @Override public String toString() { return name; }
    }

    // A MUTABLE element
    static class MutableTag {
        String name;
        MutableTag(String n) { this.name = n; }
        @Override public boolean equals(Object o) {
            return (o instanceof MutableTag t) && Objects.equals(name, t.name);
        }
        @Override public int hashCode() { return Objects.hash(name); }
        @Override public String toString() { return name; }
    }

    record Rate(String reference, double euros) { }

    public static void main(String[] args) {
        orders();
        withoutHashCode();
        mutation();
        partialComparator();
        duplicatesOnConstruction();
        performance();
    }

    static void orders() {
        System.out.println("=== 1. Three implementations, three orders ===");
        List<String> input = List.of("Magazine", "Book", "DVD", "Book", "Audiobook");
        System.out.println("Input:         " + input + "  (5 elements, one repeated)");
        System.out.println("HashSet:       " + new HashSet<>(input)       + "  unpredictable order");
        System.out.println("LinkedHashSet: " + new LinkedHashSet<>(input) + "  insertion order");
        System.out.println("TreeSet:       " + new TreeSet<>(input)       + "  alphabetical order");
        System.out.println("All three have 4 elements: 'Book' was discarded in all three.\n");
    }

    static void withoutHashCode() {
        System.out.println("=== 2. An element without hashCode ===");
        Set<BrokenTag> set = new HashSet<>();
        set.add(new BrokenTag("java"));
        set.add(new BrokenTag("java"));      // "equal" according to equals

        System.out.println("size: " + set.size() + "   <- DUPLICATES in a Set");
        System.out.println("contains(a new 'java'): "
                           + set.contains(new BrokenTag("java")) + "   <- it does not find it");
        System.out.println("Cause: hashCode inherited from Object -> each instance goes to a");
        System.out.println("different bucket and equals is NEVER executed.\n");
    }

    static void mutation() {
        System.out.println("=== 3. Mutating a stored element ===");
        MutableTag t = new MutableTag("java");
        Set<MutableTag> set = new HashSet<>();
        set.add(t);
        System.out.println("contains before: " + set.contains(t));

        t.name = "programming";                      // we mutate what is already stored

        System.out.println("contains after: " + set.contains(t) + "   <- lost");
        System.out.println("remove: " + set.remove(t) + "   <- it cannot even be taken out");
        set.add(t);
        System.out.println("size after re-adding: " + set.size()
                           + "   <- the SAME object, twice");
        System.out.println("The correct way: remove -> mutate -> add.\n");
    }

    static void partialComparator() {
        System.out.println("=== 4. A non-total Comparator in a TreeSet ===");
        // A Comparator that only looks at the euros: two different rates with the same
        // amount compare to 0, and the TreeSet considers them THE SAME element.
        Set<Rate> bad = new TreeSet<>(Comparator.comparingDouble(Rate::euros));
        bad.add(new Rate("978-0000000001", 0.25));
        bad.add(new Rate("978-0000000002", 0.25));
        System.out.println("With a partial comparator: size = " + bad.size()
                           + "   <- an element was LOST");

        Set<Rate> good = new TreeSet<>(
            Comparator.comparingDouble(Rate::euros)
                      .thenComparing(Rate::reference));    // a UNIQUE tie-breaker
        good.add(new Rate("978-0000000001", 0.25));
        good.add(new Rate("978-0000000002", 0.25));
        System.out.println("With a tie-breaker:        size = " + good.size() + "   <- correct");
        System.out.println("In a TreeSet uniqueness is decided by the COMPARATOR, not equals.\n");
    }

    static void duplicatesOnConstruction() {
        System.out.println("=== 5. Set.of versus new HashSet<>(list) ===");
        List<String> withDuplicates = List.of("Book", "Magazine", "Book");

        // Set.of("Book", "Magazine", "Book");
        //   -> IllegalArgumentException: duplicate element: Book
        //   It is deliberate: in a hand-written literal, a duplicate is a mistake.
        System.out.println("Set.of with duplicates would throw IllegalArgumentException");

        System.out.println("new HashSet<>(list): " + new HashSet<>(withDuplicates)
                           + "   <- ignores them silently");
        System.out.println("Set.copyOf(list):    " + Set.copyOf(withDuplicates)
                           + "   <- also ignores them\n");
    }

    static void performance() {
        System.out.println("=== 6. contains: List versus Set ===");
        final int N = 100_000, QUERIES = 5_000;

        List<String> list = new ArrayList<>(N);
        Set<String>  set  = new HashSet<>((int)(N / 0.75f) + 1);
        for (int i = 0; i < N; i++) {
            String ref = "978-" + String.format("%010d", i);
            list.add(ref);
            set.add(ref);
        }
        String target = "978-" + String.format("%010d", N - 1);   // the worst case: the last one

        for (int i = 0; i < 50; i++) { list.contains(target); }   // warm-up

        long t1 = System.nanoTime();
        for (int i = 0; i < QUERIES; i++) { list.contains(target); }
        long msList = (System.nanoTime() - t1) / 1_000_000;

        long t2 = System.nanoTime();
        for (int i = 0; i < QUERIES; i++) { set.contains(target); }
        long msSet = (System.nanoTime() - t2) / 1_000_000;

        System.out.printf("List.contains x%d: %6d ms%n", QUERIES, msList);
        System.out.printf("Set.contains  x%d: %6d ms%n", QUERIES, msSet);
        System.out.println("The List compares up to 100,000 times; the Set computes ONE bucket.");
    }
}

The six parts tell the same story from different angles: a Set only keeps its promise if its elements respect the contract. A missing hashCode, a mutable element or a partial comparator are three ways of breaking it, and all three fail silently: there is no exception, only duplicated or lost data. And part 6 is a reminder of why it is worth doing properly.

Solution 3

package com.nexussoftware.bibliotech.service;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

/**
 * Material tagging with a double index: material -> tags and
 * tag -> materials. Keeping both consistent is the price of
 * being able to query in both directions in O(1).
 */
public class TagManager {

    private final Map<String, Set<String>> tagsByMaterial = new HashMap<>();
    private final Map<String, Set<String>> materialsByTag = new HashMap<>();

    private static String normalise(String s) {
        return (s == null) ? null : s.trim().toLowerCase();
    }

    public void tag(String reference, String... tags) {
        if (reference == null || tags == null) { return; }
        for (String raw : tags) {
            String tag = normalise(raw);
            if (tag == null || tag.isEmpty()) { continue; }

            // computeIfAbsent creates the Set only when needed and always returns a valid one
            tagsByMaterial.computeIfAbsent(reference, r -> new HashSet<>()).add(tag);
            materialsByTag.computeIfAbsent(tag, t -> new HashSet<>()).add(reference);
            // If the tag was already there, add returns false and nothing happens: uniqueness
            // is guaranteed by the Set itself, with no checks.
        }
    }

    public Set<String> tagsOf(String reference) {
        return Set.copyOf(tagsByMaterial.getOrDefault(reference, Set.of()));
    }

    public Set<String> materialsWith(String tag) {
        return Set.copyOf(materialsByTag.getOrDefault(normalise(tag), Set.of()));
    }

    /** Successive INTERSECTION: the materials that have ALL the tags. */
    public Set<String> materialsWithAll(String... tags) {
        if (tags == null || tags.length == 0) { return Set.of(); }

        Set<String> result = new HashSet<>(materialsWith(tags[0]));
        for (int i = 1; i < tags.length; i++) {
            result.retainAll(materialsWith(tags[i]));
            if (result.isEmpty()) { break; }           // a shortcut: it can no longer grow
        }
        return result;
    }

    /** Successive UNION: the materials that have ANY of the tags. */
    public Set<String> materialsWithAny(String... tags) {
        Set<String> result = new HashSet<>();
        if (tags == null) { return result; }
        for (String t : tags) {
            result.addAll(materialsWith(t));
        }
        return result;
    }

    /** TreeSet: always in alphabetical order, with no manual sorting. */
    public Set<String> allTags() {
        return new TreeSet<>(materialsByTag.keySet());
    }

    /** Removes a tag, cleaning up entries left empty in BOTH maps. */
    public void untag(String reference, String rawTag) {
        String tag = normalise(rawTag);
        if (reference == null || tag == null) { return; }

        // Returning null from computeIfPresent removes the entry from the map (05-05)
        tagsByMaterial.computeIfPresent(reference, (r, set) -> {
            set.remove(tag);
            return set.isEmpty() ? null : set;
        });
        materialsByTag.computeIfPresent(tag, (t, set) -> {
            set.remove(reference);
            return set.isEmpty() ? null : set;
        });
    }

    public int taggedMaterials() { return tagsByMaterial.size(); }
    public int distinctTags()    { return materialsByTag.size(); }
}

A test:

TagManager g = new TagManager();
g.tag("978-0000000001", "java", "best-practices", "advanced");
g.tag("978-0000000002", "java", "patterns", "design", "advanced");
g.tag("978-0000000003", "refactoring", "design", "java");
g.tag("REV-2024-03",    "java", "news");
g.tag("DVD-0007",       "refactoring", "video");

System.out.println("Tags of 978-0000000002: " + new TreeSet<>(g.tagsOf("978-0000000002")));
System.out.println("With 'java':            " + new TreeSet<>(g.materialsWith("java")));
System.out.println("With java AND advanced: " + new TreeSet<>(g.materialsWithAll("java", "advanced")));
System.out.println("With video OR patterns: " + new TreeSet<>(g.materialsWithAny("video", "patterns")));
System.out.println("All tags: " + g.allTags());

g.untag("DVD-0007", "video");
System.out.println("After removing 'video': " + g.allTags());

Tags of 978-0000000002: [advanced, design, java, patterns]
With 'java':            [978-0000000001, 978-0000000002, 978-0000000003, REV-2024-03]
With java AND advanced: [978-0000000001, 978-0000000002]
With video OR patterns: [978-0000000002, DVD-0007]
All tags: [advanced, best-practices, design, java, news, patterns, refactoring, video]
After removing 'video': [advanced, best-practices, design, java, news, patterns, refactoring]

This exercise brings together the whole module so far. computeIfAbsent from 05-05 builds the maps of sets with not a single null check. The inner Set guarantees that tagging twice with the same thing duplicates nothing, without having to check. retainAll and addAll implement "AND" and "OR" searches that with lists would be nested loops. The TreeSet in allTags keeps alphabetical order without sorting anything. And computeIfPresent returning null cleans up the orphaned entries, stopping the maps filling with empty sets.

The price of having two indexes is keeping them consistent: every tag and every untag touches both maps. It is a deliberate trade-off —memory and discipline in exchange for O(1) queries in both directions— and it is exactly the kind of decision taken daily in the design of real systems.

Conclusion

You have now mastered the other great hash-based structure, and it cost you little because HashSet is literally a HashMap with dummy values: you have seen it in its source code, with its map field and its PRESENT sentinel. From that identity everything follows without learning anything new: O(1) for add, contains and remove; no guaranteed order; a single null; load factor, rehash and bucket-to-tree conversion; and —crucially— the same requirements about equals and hashCode as a map's keys, with the same consequences when they are broken: elements that go in and are not found, and "duplicates" in a set that is supposed to have none.

You know that a Set does not add methods to Collection but contract, and that the absence of get(i) is not a shortcoming: a set has no positions. You have learned to exploit the detail almost nobody looks at: add returns false if the element was already there, which solves in one line, and with half the work of contains + add, duplicate detection, once-per-key processing, counting distinct elements and cycle prevention.

You handle set algebra confidently: addAll for the union, retainAll for the intersection, removeAll for the difference —which is not symmetric—, containsAll for the subset and Collections.disjoint to check they share nothing; with the symmetric difference composed from the previous ones. And you have memorised the warning that avoids the most frequent mistake: the first three modify the set they are invoked on, so you always work on a copy.

You know the three implementations and the criteria for choosing: HashSet by default, LinkedHashSet for reproducible order —and for removing duplicates preserving the original order in one line—, and TreeSet when you need permanent ordering or navigation, with its whole arsenal of first, last, headSet, tailSet, subSet, ceiling, floor, higher, lower, pollFirst and descendingSet. And you know the thing most often forgotten about TreeSet: uniqueness is decided by the comparator, not by equals, so that a Comparator with no unique tie-breaking criterion silently discards different elements.

You understand the danger of mutating a stored element —it stays in the old hash's bucket, is not found, cannot be removed and can be duplicated— and its only correct solution: remove, modify, put back. You know about immutable sets, with the peculiarity that Set.of rejects duplicates with IllegalArgumentException while Set.copyOf ignores them. And you have seen with numbers the most profitable optimisation in the whole module: if you are going to check membership more than a few times, convert the list to a Set and you go from O(n×m) to O(n+m).

BiblioTech now has a DuplicateControl that rejects repeated registrations in O(1) relying solely on the boolean from add, and a NoticeManager that solves with three set operations —difference, intersection and reverse difference— what with lists would be nested loops: who has to be noticed, who is reoffending and whose notice can be withdrawn. An employee with three overdue loans receives exactly one notice, and a second pass sends none.

In the next lesson, Queue and Deque, you change family. Until now the collections answered "is it there?" and "where is it?"; now they will answer "whose turn is it?". You will see the Queue interface with its FIFO semantics and its two families of methods —the one that throws an exception and the one that returns a special value, and when to use each—, the Deque as a double-ended queue, ArrayDeque with its circular buffer and why it is the default option today (and why it rejects nulls), the PriorityQueue with its binary heap and the surprise that its iterator does not traverse in priority order, the producer-consumer pattern and breadth-first traversal. And in BiblioTech, the ReservationQueue you wrote with LinkedList will be rewritten with a Deque, and a PriorityQueue<Loan> will appear that always deals first with the loan with the most days overdue.

HashSet

Contents

What a set is

The Set interface and its API

HashSet is a HashMap in disguise

add returns a boolean, and that changes everything

Set operations

Union: addAll

Intersection: retainAll

Difference: removeAll

Subset: containsAll

Symmetric difference

Summary table

HashSet, LinkedHashSet and TreeSet

TreeSet, SortedSet and NavigableSet

Natural order or Comparator

The danger of mutating a stored element

Immutable sets

contains on a Set versus a List

Applying it to BiblioTech

A Set<String> of catalogued ISBNs

Crossing sets: overdue versus noticed

Common Mistakes and Tips

Exercises

Exercise 1: catalogue control with sets

Exercise 2: the three implementations and their traps

Exercise 3: material tags

Solutions

Solution 1

Solution 2

Solution 3

Conclusion

Java Programming Course

Module 1: Introduction to Java

Module 2: Control Flow

Module 3: Object-Oriented Programming

Module 4: Advanced Object-Oriented Programming

Module 5: Data Structures and Collections

Module 6: Exception Handling

Module 7: File Input/Output

Module 8: Multithreading and Concurrency

Module 9: Networking

Module 10: Advanced Topics

Module 11: Java Frameworks and Libraries

Module 12: Building Real-World Applications