equals and hashCode

Imagine twins, Asha and Meera. A teacher asks "Are these two the same person?" and the answer is no, they are twins. But for a school photo, the teacher says "Group the students by the colour of their shirts." Twins who dress alike must end up in the same group. If one twin wears red and the other wears blue, the photographer who looks in the "red" group for Meera will not find her.

Java has the same arrangement. Two methods that every object has, equals and hashCode, are twins that must agree.

• equals(other) answers "Are these two the same thing?" It is how Java compares content. Two students with the same id and the same name should usually count as one student.
• hashCode() returns a number, the fingerprint you met in lesson 6. A HashMap or HashSet uses it to choose a shelf.

The agreement is called the contract, which is just a rule that classes promise to follow: if two objects are equal, their hash codes must be equal too. The other way round is allowed to be loose. Two different objects can share a hash code (that is a collision, and it is fine).

Break the contract and nothing crashes. Lookups just quietly stop working, which is the worst kind of bug. This lesson shows it happen, then shows how to fix it.

Remember: if a.equals(b) is true, then a.hashCode() must equal b.hashCode(). Override both together or neither.

A hash map looks for an object in two steps. First it takes the object's hashCode() and goes to that shelf. Then, on that shelf only, it uses equals to find the exact match.

If two equal objects have different hash codes, the first step sends them to different shelves. The map goes to shelf 6 looking for b, and a is sitting on shelf 11. It never gets as far as asking equals. The picture shows this on the left. On the right, equal objects share a hash code, so they share a shelf, and equals can do its job.

The same Java feature that makes a HashSet quick is the feature that makes this bug silent. A set that checks every item would never miss. A set that trusts the shelf number depends on you keeping your promise.

Start with a class that overrides neither method.

// No equals, no hashCode: Java falls back to "same object or not".
static final class PlainStudent {
    final int id;
    final String name;

    PlainStudent(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

PlainStudent a = new PlainStudent(1, "Asha");
PlainStudent b = new PlainStudent(1, "Asha");
System.out.println(a.equals(a));
System.out.println(a.equals(b)); // same details, but two different objects
Set<PlainStudent> roll = new HashSet<>();
roll.add(a);
roll.add(b);
System.out.println(roll.size());

true
false
2

A student always equals themselves. But a and b have the same details and are still not equal. When you don't write equals, Java uses the one every object inherits, and that one asks only "is this the very same object in memory?" So a HashSet happily keeps both students, and counts 2. If you meant one student, that is wrong.

So we write our own equals. Here is a version with a classic mistake. It says two students are equal if their ids match, and it forgets that hashCode has to follow.

// The bug: equals looks only at id, but hashCode also mixes in name.
static final class BrokenStudent {
    final int id;
    final String name;

    BrokenStudent(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object other) {
        return other instanceof BrokenStudent that && id == that.id;
    }

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

equals looks at the id only. hashCode mixes in the name as well. Two students with id 1 and different names (say "Asha" and "Asha K", the same person typed two ways) are equal, but get different hash codes.

BrokenStudent a = new BrokenStudent(1, "Asha");
BrokenStudent b = new BrokenStudent(1, "Asha K");
System.out.println(a.equals(b));
System.out.println(a.hashCode() == b.hashCode());
System.out.println("buckets: " + Lesson6HashSetAndHashMap.TinyHashMap.bucketFor(a, 16)
        + " and " + Lesson6HashSetAndHashMap.TinyHashMap.bucketFor(b, 16));

true
false
buckets: 11 and 6

They are equal, their hash codes differ, and with 16 shelves they point at shelf 11 and shelf 6. (The bucketFor helper is the one from our tiny HashMap in lesson 6. Hash codes of strings come from a fixed formula, so you will see the same numbers.)

Now put one in a HashSet and ask about the other:

BrokenStudent a = new BrokenStudent(1, "Asha");
BrokenStudent b = new BrokenStudent(1, "Asha K");
Set<BrokenStudent> roll = new HashSet<>();
roll.add(a);
System.out.println(roll.contains(b)); // equal to a, yet the set looks on the wrong shelf

false

The student is in the set, and the set says no. Let us be careful about what we claim here. Java does not say what a set will do once your class breaks the contract, so the answer is "whatever happens". On the JDK these lessons use, you get false, because the set looks on the wrong shelf. You must never write code that depends on this. Treat it as a symptom to recognise.

The fix: make equals and hashCode use the same fields.

static final class Student {
    final int id;
    final String name;

    Student(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object other) {
        if (this == other) {
            return true;
        }
        // instanceof is false for null, so null needs no check of its own
        if (!(other instanceof Student that)) {
            return false;
        }
        return id == that.id && Objects.equals(name, that.name);
    }

    @Override
    public int hashCode() {
        // the same fields as equals, no more and no fewer
        return Objects.hash(id, name);
    }
}

Notice the steps in equals: return true for the same object straight away; return false if the other is not a Student (and instanceof is already false for null); then compare the fields. Objects.equals(a, b) compares two values and copes with null. Objects.hash(...) builds one hash code from several fields.

Student a = new Student(1, "Asha");
Student b = new Student(1, "Asha");
System.out.println(a.equals(b));
System.out.println(a.hashCode() == b.hashCode());
Set<Student> roll = new HashSet<>();
roll.add(a);
System.out.println(roll.contains(b));
roll.add(b);
System.out.println(roll.size());

true
true
true
1

Equal, same hash code, found in the set, and adding the second one changes nothing: the set still holds 1.

Student a = new Student(1, "Asha");
Student b = new Student(1, "Asha");
// Equal objects have equal hash codes, so they pick the same shelf.
System.out.println("buckets: " + Lesson6HashSetAndHashMap.TinyHashMap.bucketFor(a, 16)
        + " and " + Lesson6HashSetAndHashMap.TinyHashMap.bucketFor(b, 16));

buckets: 11 and 11

Both land on shelf 11, as the right-hand side of the picture promised.

Writing all of that by hand is boring, and each line is another chance for a typo. When a class is just a bundle of values, Java has a shortcut called a record.

// A record writes equals, hashCode and toString from its parts.
record Pupil(int id, String name) {}

Pupil a = new Pupil(1, "Asha");
Pupil b = new Pupil(1, "Asha");
System.out.println(a.equals(b));
System.out.println(a.hashCode() == b.hashCode());
Set<Pupil> roll = new HashSet<>();
roll.add(a);
roll.add(b);
System.out.println(roll.size());
System.out.println(a.name()); // the parts are read with name(), not getName()

true
true
1
Asha

A record writes equals, hashCode and toString for you, and it compares every part, so the two can never disagree. It also makes the parts final, which matters more than it looks (see the next section). For small data holders, such as a map key, a record is usually the best answer.

Remember: a record gets equals and hashCode for free, always in agreement. Hand-written ones must use the same fields.

The contract has a few more clauses. Memorise these five for equals, since interviewers ask for them.

• Reflexive. a.equals(a) is always true.
• Symmetric. If a.equals(b) is true, then b.equals(a) is true.
• Transitive. If a equals b and b equals c, then a equals c.
• Consistent. Asking twice gives the same answer, as long as nothing changed.
• Never equal to null. a.equals(null) is false, and must not throw.

For hashCode, the rules are shorter. The same object must give the same number each time you ask, during one run of the program. And equal objects must give equal numbers. That is the twin rule from the start of the lesson.

Two habits keep you out of trouble.

Use the same fields in both. The broken class above used one field in equals and two in hashCode. The Book and Username problems below show the opposite danger: equals ignores something (the title, or letter case), so hashCode must ignore it as well.

Don't change a key after you store it. Suppose you put a student in a HashSet, and then change the student's name. The hash code changes, but the student is still sitting on the old shelf. The set will probably look in the wrong place and lose them. The safest keys can't change at all, which is one more reason to prefer records, Strings and Integers as keys.

The cheapest hashCode that satisfies the contract returns the same number for everything. It is legal. It would also put every key on one shelf, and turn your fast map into one long chain. A good hashCode spreads different objects across many numbers.

The last two rows are the point of the lesson. A slow lookup is a performance bug. A lookup that gives the wrong answer is a correctness bug, and those are harder to find.

static final class Book {
    final String isbn;
    final String title;

    Book(String isbn, String title) {
        this.isbn = isbn;
        this.title = title;
    }

    // Two books are the same book when they share an isbn.
    // Add equals and hashCode.
}

static final class Book {
    final String isbn;
    final String title;

    Book(String isbn, String title) {
        this.isbn = isbn;
        this.title = title;
    }

    @Override
    public boolean equals(Object other) {
        // the title is left out on purpose: the isbn alone says which book this is
        return other instanceof Book that && isbn.equals(that.isbn);
    }

    @Override
    public int hashCode() {
        return isbn.hashCode(); // only the fields equals uses
    }
}

static boolean revisits(java.util.List<int[]> path) {
    throw new UnsupportedOperationException("does the path ever stand on the same square twice?");
}

// A record gives the square a working equals and hashCode. An int[]
// would not: arrays compare by identity, so two {0, 1} arrays differ.
record Square(int row, int col) {}

static boolean revisits(java.util.List<int[]> path) {
    Set<Square> seen = new HashSet<>();
    for (int[] step : path) {
        if (!seen.add(new Square(step[0], step[1]))) {
            return true;
        }
    }
    return false;
}

static final class Username {
    final String text;

    Username(String text) {
        this.text = text;
    }

    // "Asha" and "ASHA" must count as the same username.
    // Add equals and hashCode.
}

static final class Username {
    final String text;

    Username(String text) {
        this.text = text;
    }

    @Override
    public boolean equals(Object other) {
        return other instanceof Username that && text.equalsIgnoreCase(that.text);
    }

    @Override
    public int hashCode() {
        // equal usernames must hash alike, so hash the lower-case form
        return text.toLowerCase(Locale.ROOT).hashCode();
    }
}

If an interviewer asks you one HashMap question, it is usually this one.

• "Why override hashCode when you override equals?" Because hash collections find an object by shelf first and by equals second. Equal objects need equal hash codes, or they land on different shelves and a lookup misses an object that is really there.
• "What happens if you override only equals?" Equal objects may get different hash codes (the default one is tied to the object itself), so HashSet and HashMap can miss them. It is a silent bug, which is why it is worth saying out loud.
• "What happens if you override only hashCode?" Equal hash codes still lead to the right shelf, but equals then says "different object", so lookups still fail.
• "Do unequal objects need different hash codes?" No. Sharing a hash code is a collision, and is allowed. Only the other direction is a rule.
• "What makes a good hashCode?" It uses the same fields as equals, gives the same answer every time for an unchanged object, and spreads different objects across many numbers.
• "Can you use a mutable object as a key?" You can, but changing it after it is stored can lose it. Prefer immutable keys, such as String, Integer and records.
• "How do you shortcut all this?" Use a record. For a normal class, Objects.equals and Objects.hash keep the code short.
• Say the cost. "equals and hashCode each cost O(fields). With a good hash, a lookup is O(1) on average. With a broken pair, it is not slow, it is wrong."

Made by VeraStack Labs