Javanese Online

Хранение произвольных объектов в HashSet, Методы hashCode и equals

В предыдущем уроке мы разобрали множества на примере Set<Integer>. Но что, если элементы множества — не числа? Как HashSet будет определять, в какую корзину положить, например, строку или наш собственный объект?

Для сравнения объектов HashSet использует два приёма — вычисление хэш-кода (hash code) объекта и точное сравнение объектов.

Хэш-код объекта — это его числовой отпечаток, который можно получить, вызвав метод hashCode(). Если у двух объектов разные хэш-коды, то содержимое объектов должно различаться. Обратное утверждение не всегда верно — у двух разных объектов может быть различное содержимое и одинаковые хэш-коды, такое явление называется коллизией.

Точное сравнение производится вызовом метода boolean equals(Object other), который возвращает true, если объекты равны.

По умолчанию реализации методов hashCode и equals наследуются от Object, и разные объекты имеют разные хеш-коды и считаются не равными друг другу.

Есть мнение, что Object#hashCode() возвращает адрес объекта в памяти. Это неверно: в процессе сборки мусора объект перемещается, а хэш-код остаётся неизменным. Есть способ заставить JVM считать хэш-код по адресу рождения объекта, но он имеет смысл только для исследовательских целей.

class Something {}
...
System.out.println(new Something().hashCode()); // 856419764
System.out.println(new Something().hashCode()); // 621009875
System.out.println(new Something().hashCode()); // 1265094477
System.out.println(new Something().equals(new Something())); // false
System.out.println(new Something().equals(new Something())); // false

Соответственно, добавление этих объектов будет происходить таким образом:

Set<Something> set = new HashSet<>();
set.add(new Something()); // true — новый элемент добавлен
Something some = new Something();
set.add(some); // true — добавлен
set.add(some); // false — такой объект уже есть

А вот у класса String эти методы переопределены.

System.out.println("first".hashCode()); // 97440432
System.out.println("second".hashCode()); // -906279820
System.out.println("first".hashCode()); // 97440432
System.out.println("first".equals("second")); // false
System.out.println("first".equals("first")); // true

Следовательно, одна строка (или две одинаковых строки) два раза в один Set не добавится:

Set<String> set = new HashSet<>();
set.add("whatever"); // true
set.add("whatever"); // false
set.add(new String("whatever")); // false

HashSet<String> изнутри

Переопределение hashCode()

Раз наш класс Something не содержит данных, то все экземпляры равны между собой и имеют одинаковый хэш-код.

public final class Something {

    @Override
    public int hashCode() {
        return 1;
    }

    @Override
    public boolean equals(Object other) {
        if (this == other) {
            return true;
        // переданный объект — это this, нечего проверять
        }

        if (o == null || o.getClass() != getClass()) {
            return false; // возвращаем false,
            // если переданный объект не является экземпляром Something
        }

        return true; // other — экземпляр Something,
        // а все они равны между собой. Больше нечего проверять
    }
}

Теперь поведение HashSet изменится:

Set<Something> set = new HashSet<>();
set.add(new Something()); // true — новый элемент добавлен
set.add(new Something()); // false — уже есть такой

Если объект таки хранит данные (а именно так и бывает), над hashCode и equals придётся поработать.

Для примера возьмём класс Point:

public final class Point {

    private final double x;
    private final double y;

    ...

В IntelliJ IDEA нажать Code -> Generate -> equals() and hashCode(), откроется мастер, который поможет сгенерировать код для этих рутинных операций.

Метод equals

Разберём сгенерированный метод equals:

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    // если передан объект другого класса, считаем, что он не равен данному

    Point point = (Point) o;

    // сравниваем значения полей по очереди
    if (Double.compare(point.x, x) != 0) return false;
    return Double.compare(point.y, y) == 0;
}

Методы Float.compare и Double.compare используют для сравнения дробных чисел, т. к. сравнение «в лоб» (==) не всегда работает с ними правильно.

Теперь разберём метод hashCode:

Метод hashCode

Хэш-код — это четырёхбайтное целое (int). Чтобы посчитать хэш-код объекта, нужно сначала посчитать хэш-коды всех его полей, а затем совместить их.

Чтобы посчитать хэш-код значения с плавающей точкой, сначала нужно привести его к целому. И сделать это нужно не отбрасывая дробную часть. Для этого есть статические методы Float.floatToIntBits и Double.doubleToLongBits, которые возвращают «сырые» значения чисел.

Чтобы посчитать хэш-код восьмибайтного числа, нужно произвести исключающее побитовое «или» (xor) старшей половины числа с младшей: (int) (x ^ (x >>> 32)).

Для максимальной энтропии (разброса значений) хэш-кодов значения умножаются на 31 перед сложением. Простой множитель 31 найден опытным путём. Подробное разъяснение (en).

int hashCode = field1.hashCode();
hashCode = 31 * hashCode = field2.hashCode();
hashCode = 31 * hashCode = field3.hashCode();

В итоге IntelliJ IDEA сгенерирует такой метод hashCode() для класса Point:

@Override
public int hashCode() {
    int result;
    long temp;
    temp = Double.doubleToLongBits(x);
    result = (int) (temp ^ (temp >>> 32));
    temp = Double.doubleToLongBits(y);
    result = 31 * result + (int) (temp ^ (temp >>> 32));
    return result;
}

Меры предосторожности

См. также Joshua Bloch, Effective Java

Комментарии к уроку

Сообщить об ошибке

Javanese.Online в GitHub

Чаты и каналы в Telegram

RSS-лента