HashSet, equals and hashCode

A cloakroom holds hundreds of coats. If the attendant looked for yours by going through them all, the line would last until the end of the show. So every coat hangs on a numbered hook, and you hold a numbered tag. With the tag, the attendant goes straight to the right hook and only has to check the coats hanging there.

A list looks for an element exactly by "going through them all": contains on an ArrayList compares what you look for with each element in turn. In a list of a million elements, that is up to a million comparisons. The set HashSet searches like the attendant:

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

public class Main {
    public static void main(String[] args) {
        Set<String> guests = new HashSet<>();
        System.out.println(guests.add("Anna"));       // true
        System.out.println(guests.add("Boris"));      // true
        System.out.println(guests.add("Anna"));       // false
        System.out.println(guests.size());           // 2
        System.out.println(guests.contains("Boris")); // true
    }
}

Let's go through the program line by line:

1. Set<String> guests = new HashSet<>(); creates an empty set of strings. Set is an interface and HashSet a class, like List and ArrayList.
2. add returns true when the element is added.
3. The second add("Anna") returns false: that string is already there, and the set does not add it.
4. guests.size() returns 2: the repeat did not get in.
5. guests.contains("Boris") answers true.

A set has no repeats

A set is a collection in which each element appears at most once. How a Set differs from a List is a common interview question:

• a set has no repeats, while a list can have any number of them;
• a set has no indices and no get(i) method;
• HashSet does not keep the order of adding, so you cannot rely on the order of its elements.

You take a set when what matters is whether an element is there, not where it stands: whether a guest came to the party, which words appear in a text.

hashCode first, then equals

Every object has a hashCode method: all classes got it from Object. It returns a number, the object's hash code. HashSet looks for an element in two steps:

1. It calls hashCode and uses that number to choose a hook, one of its slots.
2. Among the elements on that hook, it looks for an equal one: it compares hash codes and calls equals only on an element with the same hash code.

So contains does not go through the whole set; it looks at one hook, which usually holds one element or two. String and Integer override both methods: equal strings give equal hash codes.

Point without hashCode

In the wrappers and equality theme, the class Point learned to compare coordinates with equals, while hashCode was left from Object. Let's put such a point into a set and look for an equal one:

Set<Point> set = new HashSet<>();
set.add(new Point(1, 2));
System.out.println(set.contains(new Point(1, 2))); // false

The points are equal by equals, and still the set finds nothing. hashCode from Object does not look at the fields: it gives a number to the object itself, and two different objects almost never get the same one. The hash codes differ, so equals is never reached. The attendant searches by tag, and two identical coats have different tags. This is what javac warned about with the -Xlint:all flag in that same theme.

The equals and hashCode contract

This leads to a rule called the equals and hashCode contract:

• if a.equals(b) gives true, then a.hashCode() and b.hashCode() must be the same;
• the reverse is not required: unequal objects may share a hash code too, and then they hang on one hook.

This is a classic interview question. The short answer: override equals, and override hashCode too, over the same fields. There is the method Objects.hash from java.util for this. Let's add to the class Point:

@Override
public int hashCode() {
    return Objects.hash(x, y);
}

Objects.hash(x, y) builds one number from the fields, so equal points get equal hash codes. List in it the same fields that equals compares. With this method, the program from the last section prints true. Records from the records theme write equals and hashCode themselves, so you can put them into a HashSet right away.

Here the cloakroom picture is not exact. In a real cloakroom the attendant hands out the tags, and two identical coats get different ones. In Java the object computes its number from its own fields, so two equal objects must come with the same number.

Common mistake

A field was changed on a point that already sits in the set:

Set<Point> set = new HashSet<>();
Point p = new Point(3, 4);
set.add(p);
p.x = 5; // ✗
System.out.println(set.contains(p)); // false

The point hangs on the hook that the hash code of (3, 4) chose. After p.x = 5 the hash code is different, and HashSet looks the point up by the new number while it hangs under the old one. The object is still in the set, but now it cannot be found: neither through p nor through new Point(3, 4). The new point comes with the old number, but equals does not find it equal to the point (5, 4). It is like changing the number on your tag after the coat is already hanging.

Do not change the fields hashCode depends on while the object sits in a HashSet. It is safer to make them final or to use a record.

Key points

• HashSet keeps each element once: a repeated add returns false, and a set has no indices and no order.
• An element is found in two steps: hashCode chooses where to look, and equals finds the equal element there.
• The contract: objects equal by equals must have equal hashCodes, so hashCode is overridden together with equals, for example with Objects.hash.
• Without its own hashCode, an equal object is not found in a HashSet; the same happens if you change a field of an object that is already in the set.