05 — equals, hashCode & Using Objects as Keys

HashMap and HashSet are the two most-used structures in the 150. Both depend entirely on two methods — equals and hashCode — and Java's defaults are almost never what you want for a custom class.

Getting this wrong produces the worst kind of bug: no exception, no warning, just lookups that silently return null for keys you know you inserted.

Every behaviour claimed here was verified by running it.

How a HashMap actually finds things

Two steps, and each uses a different method:

1. hashCode() → an int, reduced to a bucket index. This says where to look.
2. equals() → compares against the few entries in that bucket. This says which one it is.

key.hashCode()  =  98123     →  bucket 7
                                  │
      bucket 7: [ entryA ] → [ entryB ]      ← walk this short chain,
                                                calling equals() on each

Both are required. If hashCode sends you to the wrong bucket, equals is never even consulted.

That single fact explains every trap below.

The contract

1. If a.equals(b) is true, then a.hashCode() == b.hashCode() must be true.
2. If a.hashCode() == b.hashCode(), a.equals(b) may be false (a collision — allowed and normal).
3. Both must be consistent: repeated calls return the same result while the object is unmodified.

Rule 1 is the one that breaks code. Equal objects landing in different buckets means the map can never find them.

Rule 2 being one-directional is why collisions are fine — the bucket chain resolves them with equals.

The defaults, and why they fail

Object's implementations are:

• equals — reference equality (this == other). Two distinct objects are never equal, however identical their contents.
• hashCode — derived from the object's identity, effectively its memory address.

So a class that overrides neither behaves like this:

class NoEq { int v; NoEq(int v) { this.v = v; } }

Set<NoEq> set = new HashSet<>();
set.add(new NoEq(1));
set.add(new NoEq(1));
set.size();          // 2  ← verified

Two objects with identical contents, both stored. For a value-like class, that's a bug.

Overriding equals but not hashCode — the classic disaster

class WithEq {
    int v;
    WithEq(int v) { this.v = v; }
    @Override public boolean equals(Object o) {
        return o instanceof WithEq && ((WithEq) o).v == v;
    }
    // hashCode NOT overridden
}

Set<WithEq> set = new HashSet<>();
set.add(new WithEq(1));
set.contains(new WithEq(1));      // false  ← verified

The object is in the set, and the set says it isn't.

Why: the two objects are equals, but their inherited hashCodes differ, so contains computes a different bucket and finds nothing there. equals is never called.

This is why IDEs generate the two methods together, and why "override equals without hashCode" is flagged by every static analyser.

Writing them correctly

class Employee {
    int id;
    String name;
    String dept;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;                       // fast path
        if (o == null || getClass() != o.getClass()) return false;
        Employee other = (Employee) o;
        return id == other.id                             // primitives: ==
            && Objects.equals(name, other.name)           // objects: null-safe equals
            && Objects.equals(dept, other.dept);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name, dept);              // SAME fields as equals
    }
}

The four parts of equals:

1. this == o — identity shortcut, cheap and common.
2. Null and type check. getClass() != o.getClass() is strict; o instanceof Employee is laxer and allows subclasses. Either is defensible — getClass is safer for value types.
3. Cast — safe now that the type is confirmed.
4. Compare fields — == for primitives, Objects.equals for references (it handles nulls, unlike a.equals(b) which throws if a is null).

hashCode must use exactly the same fields as equals. Using more fields breaks rule 1; using fewer just causes extra collisions (correct but slower).

Objects.hash(...) handles the combining. Writing it by hand looks like:

int result = 17;
result = 31 * result + id;
result = 31 * result + (name == null ? 0 : name.hashCode());
return result;

31 is used because it's an odd prime and 31 * x compiles to a shift-and-subtract. Know the idiom; use Objects.hash in practice.

Records generate both for free

record Employee(int id, String name, String dept) {}

A record automatically gets equals, hashCode, toString, and accessors, all based on all its components. For a value-like key type in an interview, this removes the whole issue — mention it if your language level allows records (Java 16+).

Using objects as keys in DSA problems

int[] does NOT work as a HashMap key

This is the most common Java-specific failure in the 150. Arrays do not override equals or hashCode — they use identity.

Map<int[], String> map = new HashMap<>();
int[] k = {1, 2};
map.put(k, "v");

map.get(k);                  // "v"    ← same reference, works
map.get(new int[]{1, 2});    // null   ← verified: equal contents, different object

So Map<int[], ...> only ever works if you keep the exact reference — which defeats the purpose. Never use a raw array as a key.

The same applies to Set<int[]>: it will happily store a thousand copies of {1, 2}.

What to use instead

// List as a key — verified to work by content
Map<List<Integer>, String> m = new HashMap<>();
m.put(List.of(1, 2), "v");
m.get(List.of(1, 2));                    // "v"  ✓
List.of(1,2).equals(Arrays.asList(1,2)); // true — List equality is by content, not by class

// Encoding two ints into one long — from Detect Squares ([23](23-math-and-geometry.md))
private long key(int x, int y) {
    return ((long) x << 32) | (y & 0xFFFFFFFFL);
}

The & 0xFFFFFFFFL mask stops a negative y from sign-extending into the high 32 bits and corrupting the encoded x. Without it, key(1, -1) and key(0, -1) collide.

// Count signature as a key — from Group Anagrams ([06](06-arrays-and-hashing.md))
int[] count = new int[26];
for (char c : word.toCharArray()) count[c - 'a']++;
String key = Arrays.toString(count);     // "[1, 0, 0, ...]" — a String, so content-based

That Arrays.toString is not decoration — it's what makes the key work at all. Using the int[] directly would put every word in its own group.

Mutating a key destroys the entry

Map<List<Integer>, String> m = new HashMap<>();
List<Integer> key = new ArrayList<>(List.of(1, 2));
m.put(key, "v");

key.add(3);                  // mutate the key AFTER insertion
m.get(key);                  // null   ← verified
m.size();                    // 1      — the entry is still there, just unreachable

The entry sits in the bucket for the old hash, while lookups now compute the new hash. It's leaked — present in size(), invisible to get.

Rule: never mutate an object after using it as a key. Either use immutable keys (List.of, String, boxed primitives, records with final fields), or copy before inserting: m.put(new ArrayList<>(key), v).

The same hazard applies to HashSet elements.

The classes you get for free

These already implement both methods correctly, so they're always safe as keys:

String, Integer, Long, Double, Character, Boolean, all boxed primitives, all enums, List implementations (ArrayList, List.of), Set implementations, Map implementations, and records.

Not safe: arrays of any type (int[], String[], int[][]), and any custom class that doesn't override them.

Arrays.equals(a, b) and Arrays.hashCode(a) exist as static helpers — but HashMap never calls them, because it calls the instance methods on the key. They're for explicit comparison only, and Arrays.deepEquals/deepHashCode handle nested arrays.

equals vs compareTo — two different notions of "same"

They can disagree, and that causes real bugs:

TreeSet<Employee> ts = new TreeSet<>(Comparator.comparing(e -> e.dept));
// four employees across two departments
ts.size();     // 2  ← verified: two silently dropped

The comparator returned 0 for same-department employees, so the TreeSet called them duplicates — even though equals would have said they're different people. A HashSet would have kept all four.

The standard advice: keep compareTo consistent with equals — compareTo returns 0 exactly when equals returns true. When you deliberately break that (a comparator that only orders by one field), never use it in a sorted set or as map keys without a unique tie-breaker:

new TreeSet<>(Comparator.comparing((Employee e) -> e.dept)
                        .thenComparingInt(e -> e.id));    // id makes it a total order

See 04 for the full treatment.

BigDecimal is the famous standard-library violation: new BigDecimal("1.0").equals(new BigDecimal("1.00")) is false (different scale), but compareTo returns 0. So a HashSet keeps both and a TreeSet keeps one.

Debugging checklist

When a HashMap or HashSet "loses" your data:

1. Did you override hashCode as well as equals? Missing hashCode is the number-one cause.
2. Do both methods use the same fields?
3. Is the key an array? Arrays use identity — switch to List, String, or an encoded long.
4. Did you mutate the key after inserting? The entry is unreachable.
5. Is equals taking Object as its parameter? boolean equals(Employee o) overloads rather than overrides — the collection still calls the Object version. Add @Override and the compiler will catch it.
6. For a sorted collection: is it deduplicating by comparator instead of equals?

@Override on both methods is not optional discipline — it's a compile-time check. It catches the wrong-parameter-type mistake, which is otherwise invisible.

Quick reference