HashSet, equals и hashCode

В гардеробе сотни пальто. Если бы гардеробщик искал ваше, перебирая все подряд, очередь стояла бы до конца спектакля. Поэтому каждое пальто висит на крючке с номером, а у вас в руке номерок. По номерку гардеробщик сразу идёт к нужному крючку, и проверить ему остаётся только пальто, которые висят там.

Список ищет элемент как раз «все подряд»: contains у ArrayList сравнивает искомое с каждым элементом по очереди. В списке из миллиона элементов это до миллиона сравнений. Множество HashSet ищет как гардеробщик:

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
    }
}

Давайте разберём программу по строкам:

1. Set<String> guests = new HashSet<>(); создаёт пустое множество строк. Set — интерфейс, HashSet — класс, как List и ArrayList.
2. add возвращает true, когда элемент добавлен.
3. Второй add("Anna") возвращает false: такая строка уже есть, и множество её не добавляет.
4. guests.size() возвращает 2: повтор не попал внутрь.
5. guests.contains("Boris") отвечает true.

Множество без повторов

Множество — коллекция, в которой каждый элемент встречается не больше одного раза. Чем Set отличается от List, часто спрашивают на собеседовании:

• в множестве нет повторов, а в списке их может быть сколько угодно;
• у множества нет индексов и метода get(i);
• HashSet не хранит порядок добавления, поэтому на порядок его элементов полагаться нельзя.

Множество берут, когда важно, есть ли элемент, а не где он стоит: был ли гость на вечере, какие слова встретились в тексте.

Сначала hashCode, потом equals

У каждого объекта есть метод hashCode: все классы получили его от Object. Он возвращает число — хеш-код объекта. HashSet ищет элемент в два шага:

1. Вызывает hashCode и по этому числу выбирает крючок, одну из своих ячеек.
2. Среди элементов на этом крючке ищет равный: сравнивает хеш-коды и вызывает equals только у элемента с тем же хеш-кодом.

Поэтому contains не перебирает всё множество, а смотрит на один крючок, где обычно висит один элемент или два. У String и Integer оба метода переопределены: равные строки дают равные хеш-коды.

Point без hashCode

В теме об обёртках и равенстве класс Point научили сравнивать координаты через equals, а hashCode оставили от Object. Положим такую точку в множество и поищем равную ей:

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

Точки равны по equals, а множество не находит ни одной. hashCode из Object не смотрит на поля: он выдаёт число самому объекту, и у двух разных объектов эти числа почти никогда не совпадают. Хеш-коды разные, поэтому до equals дело не доходит. Гардеробщик ищет по номерку, а номерки у двух одинаковых пальто разные. Об этом и предупреждал javac с флагом -Xlint:all в той же теме.

Контракт equals и hashCode

Отсюда правило, которое называют контрактом equals и hashCode:

• если a.equals(b) даёт true, то a.hashCode() и b.hashCode() обязаны совпадать;
• обратное не требуется: у неравных объектов хеш-коды тоже могут совпасть, и тогда они висят на одном крючке.

Это классический вопрос на собеседовании. Короткий ответ: переопределили equals — переопределите и hashCode, по тем же полям. Для этого есть метод Objects.hash из java.util. Допишем в класс Point:

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

Objects.hash(x, y) собирает из полей одно число, поэтому равные точки получают равные хеш-коды. Перечислите в нём те же поля, что сравнивает equals. С этим методом программа из прошлого раздела печатает true. Записи record из темы о записях пишут equals и hashCode сами, поэтому их можно класть в HashSet сразу.

Здесь картинка с гардеробом неточна. В настоящем гардеробе номерок выдаёт гардеробщик, и у двух одинаковых пальто номерки разные. В Java номер считает сам объект по своим полям, поэтому два равных объекта обязаны прийти с одним номером.

Частая ошибка

Поменяли поле точки, которая уже лежит в множестве:

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

Точка висит на крючке, который выбрал хеш-код от (3, 4). После p.x = 5 хеш-код другой, и HashSet ищет точку по новому номеру, а она висит под старым. Объект остался в множестве, но найти его теперь нельзя: ни по p, ни по new Point(3, 4). Новая точка придёт со старым номером, но equals не признает её равной точке (5, 4). Это как сменить номер на номерке, когда пальто уже висит.

Не меняйте поля, от которых зависит hashCode, пока объект лежит в HashSet. Надёжнее сделать их final или взять запись.

Главное

• HashSet хранит каждый элемент один раз: повторный add возвращает false, индексов и порядка у множества нет.
• Элемент ищут в два шага: hashCode выбирает, где искать, а equals находит равный элемент там.
• Контракт: объекты, равные по equals, обязаны иметь равный hashCode, поэтому вместе с equals переопределяют hashCode, например через Objects.hash.
• Без своего hashCode равный объект в HashSet не находится; то же случится, если поменять поле объекта, который уже лежит в множестве.