HashSet, equals, and hashCode

HashSet: no duplicates

"Have I seen this before?" is its own recurring problem — duplicate email signups, already-visited pages in a crawler, repeated words in a document. A list answers it by scanning everything, which turns a million-item check into a million comparisons per question. A HashSet stores each value at most once, like Python's set, and answers membership immediately. The detail that makes it so convenient in practice: add reports whether the value was new — true if it went in, false if it was already there — so checking and recording become a single call.

import java.util.HashSet;

HashSet<String> seen = new HashSet<>();
seen.add("x")        // true, newly added
seen.add("x")        // false, already present
seen.contains("x")   // true
seen.size()          // 1

contains runs in constant time regardless of size, using the same bucket trick as HashMap in lesson 7-2. "Have I seen this before?" questions that would need a slow nested loop with lists become one-liners.

equals and hashCode, gently

How does a set know two objects are "the same"? Two methods every object carries:

• equals(other): are these logically equal?
• hashCode(): which bucket does this belong in?

String, Integer, and the other built-ins define both correctly, which is why sets and map keys of Strings just work. Your own classes inherit the defaults, which say "equal only if the exact same object". So two new Point(3, 4) objects would count as different set members.

The rule to remember now: if a class is used as a HashMap key or HashSet element, it must override both equals and hashCode, and equal objects must produce equal hash codes. IDEs and record types generate them for you. We stick to String and Integer keys in this course.