HashSet, equals, and hashCode

HashSet, no duplicates

Asking whether something has been seen 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.

One detail makes it especially convenient. add reports whether the value was new, returning true if it went in and false if it was already there, so checking and recording collapse into 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 the HashMap in lesson 7-2. A set is essentially a map that keeps only the keys.

Questions of the "have I seen this" kind that would need a slow nested loop with lists become one-liners here.

What add reports

Three adds, one of them a repeat, and a size that counts only distinct values.

import java.util.HashSet;

public class Main {
  public static void main(String[] args) {
    HashSet<String> seen = new HashSet<>();
    System.out.println(seen.add("alpha"));
    System.out.println(seen.add("beta"));
    System.out.println(seen.add("alpha"));
    System.out.println(seen.contains("alpha"));
    System.out.println(seen.size());
  }
}

Output

true
true
false
true
2

The third add returned false, and the duplicate did not inflate the size, which stays at 2 after three calls.

A rejected add is not an error and throws nothing, so ignoring the return value is perfectly normal when you only want the set to end up holding distinct values.

How a set decides two things are the same

Two methods every object carries answer that question:

• equals(other), asking whether these are logically equal.
• hashCode(), deciding which bucket this belongs in.

String, Integer, and the other built-ins define both correctly, which is why sets and map keys made of Strings simply work.

Your own classes inherit the defaults, which say "equal only if this is the exact same object". Two separate new Point(3, 4) objects therefore count as different set members even though they carry identical data.

The rule to remember now: a class used as a HashMap key or HashSet element must override both equals and hashCode, and equal objects must produce equal hash codes.

Overriding only one is worse than overriding neither. Matching equals with a default hashCode sends two equal objects to different buckets, so the set never compares them and silently keeps both.

IDEs and record types generate the pair for you. This course sticks to String and Integer keys.

A class with no overrides as a set element

Given class Point { int x; int y; } with no overrides, adding new Point(3, 4) twice to a HashSet leaves a size of 2.

Without overriding equals and hashCode, Java compares identity, and two separately constructed Points are different objects, so both are kept.

Overriding both methods fixes it, and a record Point(int x, int y) generates them automatically, which is the modern shortcut for exactly this kind of value type.

The failure is quiet, which is what makes it dangerous. Nothing errors, the set just fills up with duplicates that it does not recognize as duplicates.

Finding the first repeated word

One loop, using the return value of add as the duplicate test.

import java.util.HashSet;

public class Main {
  public static void main(String[] args) {
    String[] words = { "red", "blue", "red", "green", "blue" };
    HashSet<String> seen = new HashSet<>();
    for (String w : words) {
      if (!seen.add(w)) {
        System.out.println("repeat: " + w);
        break;
      }
    }
  }
}

Output

repeat: red

seen.add(w) returns false exactly when w was already present, so negating it with if (!seen.add(w)) both detects the duplicate and records new words in one move.

break from lesson 3-3 stops the loop at the first repeat, so the second blue is never reported. Without the set this would need a nested loop comparing every word against every earlier word, which is the slow version this pattern replaces.