Урок 22. hashcode и equals в Java: часть 2

Это вторая часть урока из нашей серии уроков Java для начинающих. На этом уроке мы говорим о сравнениях и хэшах.

Коллекции и хэши

В Java подобные объекты обычно помещаются в “коллекцию” для обработки. Коллекции Java похожи на более мощные массивы, или “массивы на стероидах”! Кроме всего прочего, они позволяет нам искать объекты не только по положению, но и по их конкретным значениям. Именно здесь в игру вступает метод equals. Чтобы ускорить поиск, создатели Java добавили специальные контейнеры на основе хэша, которые используют хэш-значение в качестве механизма группировки, чтобы уменьшить количество необходимых равных сравнений. В идеале объекты, считающиеся неравными равными, будут возвращать различные хэш-коды, которые используются для группировки объектов в “ведра” (корзины, bucket). В этом идеальном случае мы сможем найти каждый объект просто путем поиска, основанного на его хэш-значении.

Хэш-коллизии

Однако существуют “хэш-коллизии”, которые возникают из-за двух неравных объектов, использующих один и тот же хэш-код; в этом случае они оказываются в одном и том же ведре. Если мы ищем, скажем, экземпляр dadsCar, мы должны найти правильное ведро, основанное на хэш-коде минус 391, который вернет dadsCar. Однако при столкновении хэшей нам придется сделать равное сравнение в списке из двух автомобилей поверх получения хэш-кодов.

Реализация хэш-кода поставляется с двумя правилами. Первый из них - это:

“Для любых двух объектов возвращайте один и тот же хэш-код, когда equals возвращает true.”

Для достижения этой цели мы используем одни и те же идентифицирующие атрибуты для обоих методов в одном и том же порядке. Второе условие - это:

“Когда хэш-код вызывается более одного раза и для одного и того же объекта, он должен последовательно возвращать одно и то же значение int до тех пор, пока объект не будет изменен.”

Это правило аналогично правилу согласованности equals, введенному ранее. Оба метода equals и hashCode должны возвращать согласованные результаты.

Чтобы выполнить этот контракт, вы должны перезаписать хэш-код всякий раз, когда вы перезаписываете equals и наоборот. Кроме того, когда вы добавляете или удаляете атрибуты из своего класса, вам придется настроить свои методы equals и hashCode. И последнее, но не менее важное: стремитесь возвращать разные хэш-коды, когда equals возвращает false. Стремление возвращать различные хэш-коды не является жестким и быстрым правилом, но оно улучшит производительность вашей программы, минимизировав количество хэш-коллизий. Взятый в крайнем случае, контракт хэш-кода позволяет нам статически возвращать значение заполнителя, такое как 42 для всех объектов. Однако, как утверждает Джош блох в своей книге "Эффективная Java", это может привести к квадратичному, а не линейному времени выполнения.

Метод хэш-кода на самом деле довольно сложный зверь. Он имеет такой уровень сложности, что если бы существовали новые, значительно превосходящие алгоритмы для хэширования до 32-битного целого числа, как в случае с Java, такое открытие, вероятно, заработало бы самые высокие награды и награды в области компьютерных наук. Некоторые из алгоритмов Джоша Блоха являются некоторыми стандартами, которые мы используем в Java для хэширования, как мы увидим в последующих примерах.

Реализация HashCode и Equals

public class Car {

    private Vin vehicleIdentificationNumber;
    private Manufacturer manufacturer;
    private Engine engine;
    private Color color;
    private int numberOfWheels;

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        Car other = (Car) obj;
        if (!manufacturer.equals(other.manufacturer)) {
            return false;
        }
        if (!engine.equals(other.engine)) {
            return false;
        }
        if (!color.equals(other.color)) {
            return false;
        }
        return true;
    }

    @Override
    public int hashCode(){...}
}

Поля произвольно выбираются в соответствии с фазой имитационного проектирования в нашем теоретическом обсуждении, потому что они имеют смысл для наших бизнес-сценариев. Следовательно, мы игнорируем использование других полей, таких как numberOfWheels и VIN для этих двух методов. Обратите внимание, что порядок, в котором они сравниваются, также произволен.

Для нашего сценария мы сначала сравниваем производителей, затем двигатели и, наконец, цвет. Если мы сравниваем два объекта, которые не равны, мы хотим покинуть метод как можно раньше, потому что чем раньше мы уйдем, тем быстрее будет выполняться весь код. В нашем сценарии мы знаем, что существует множество производителей, поэтому мы можем быстро вернуть false для автомобилей, которые, скорее всего, будут иметь разных производителей.

В нашем примере двигатели, скорее всего, будут одинаковыми, так как многие производители используют одни и те же двигатели для многих автомобилей. Несмотря на то, что на самом деле существуют миллионы цветов, мы исходим из предположения, что существует только так много работ по покраске и отделке, которые могут прийти в автомобили. Таким образом, мы избегаем еще более высокой вероятности появления автомобилей одного цвета. То, что мы в конечном итоге имеем, - это порядок сравнения, где мы оптимизируем, начиная с наиболее вероятного неравенства и заканчивая наименее вероятным, то есть сравнивая производителей, затем двигатели и, наконец, цвета. В идеале, тесты производительности на реальных наборах данных укажут нам на наилучшую реализацию.

Теперь, когда мы можем привести obj к Car, мы можем сравнить их по их частным полям – что мы можем сделать, потому что оба являются экземплярами одного и того же класса. Это позволяет нам легко сказать, что engine.equals(other.engine), что делает код гораздо более читабельным и коротким. Для каждой пары полей, которые мы сравниваем, мы можем непосредственно оставить метод, когда они неравны. Только когда мы пройдем через все поля, не возвращая ложь, мы сможем вернуть истину. Обратите внимание, что мы не сравниваем количество колес, а также номер идентификации транспортного средства. Во-первых, это потому, что у нас есть автомобили, которые всегда имеют четыре колеса в нашем примере. Во-вторых, мы могли бы иметь два физически идентичных автомобиля, скажем, оба синих BMW с одинаковым двигателем, и мы все равно рассматривали бы их как один и тот же автомобиль в нашей программе.

@Override
    public int hashCode() {
        int result = 1;
        result = 31 * result + manufacturer.hashCode();
        result = 31 * result + engine.hashCode();
        return 31 * result + color.hashCode();
    }

До сих пор мы знали, что реализация хэш-кода довольно сложна. Чтобы понять важность 31-й константы, нам нужно рассмотреть несколько деталей. 31-это простое число, которое можно очень быстро умножить с помощью сдвига и вычитания следующим образом: 31 * i == (i << 5) – i, и, согласно исследованиям, оно обеспечивает лучшее распределение ключей, которое минимизирует количество хэш-коллизий. В коде выше 31 последовательно умножается на накопленный результат, добавляя хэш-коды трех полей, которые мы использовали ранее для равенства. Все это оптимизирует производительность нашего кода, сводя к минимуму коллизии.

Как вы можете видеть, этот метод на самом деле не делает ничего, кроме делегирования вычисления хэш-кода другим классам, представляющим части нашего автомобиля. Из этих трех классов давайте подробно рассмотрим движок, чтобы увидеть, как хэш-код реализуется более подробно.

public class Engine {

    private long type;

    private String optionalField;

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        Engine other = (Engine) obj;

        if (type != other.type) {
            return false;
        }
        if (optionalField == null) {
            if (other.optionalField != null) {
                return false;
            }
        } else if (!optionalField.equals(other.optionalField)) {
            return false;
        }
        return true;
    }

    @Override
    public int hashCode() {
        int result = 1;
        result = 31 * result + (int) (type ^ (type >>> 32));
        return 31 * result + ((optionalField == null) ? 0
            : optionalField.hashCode());
    }
}

Метод equals Engine аналогичен методу Car, заметным отличием которого является проверка на null в поле optionalField. Мы должны сделать несколько несколько более сложных нулевых проверок переменных optionalField обоих объектов, чтобы предотвратить любое исключение NullPointerException. Однако с необязательными примитивными полями нам не нужно проверять наличие нулей. Мы не делаем таких же предположений в отношении обязательных полей, таких как производитель, двигатель и цвет, поэтому мы также не делаем нулевых проверок для них. Это приведет к загромождению кода “ракетным кодом”, что сделает его более безопасным, но грязным. Что касается хэш-кода, то мы преобразуем тип переменной long field в int, как показано. Поскольку longs имеют 64 бита, а int-только 32, мы каким-то образом сокращаем тип вдвое, чтобы минимизировать коллизии.

Чтобы понять, как это делается, нам нужно посмотреть на (int) (type ^ (type >>> 32)). Во-первых, мы делаем побитовый сдвиг с оператором >>> на типе более 32 бит. Это перемещает первые 32 бита типа к его последним 32 битам. Во-вторых, мы делаем “исключающее ИЛИ” ИЛИ “xor” с оператором^, который эффективно сохраняет и объединяет некоторую информацию из двух половин типа, гарантируя, что мы минимизируем коллизии, когда мы наконец опустим наш длинный тип до int. Обратите внимание, что это текущий стандарт для хэширования длинных полей. Мы делаем примерно то же самое, что и с хэш-кодом автомобиля, и накапливаем полученный хэш.

@Override
    public int hashCode() {
        int result = 0;
        result = 31 * result + myByte;
        result = 31 * result + myShort;
        result = 31 * result + myInt;
        result = 31 * result + (int) (myLong ^ (myLong >>> 32));
        result = 31 * result + Float.floatToIntBits(myFloat);

        long temp = Double.doubleToLongBits(myDouble);
        result = 31 * result + (int) (temp ^ (temp >>> 32));
        result = 31 * result + (myBoolean ? 1231 : 1237);
        result = 31 * result + myChar;
        return 31 * result + myString.hashCode();
    }
}

Код выше - это специальный пример, который более подробно иллюстрирует реализацию хэш-кода с примитивными типами. Мы видим, что используется одно и то же стандартное хеширование длинных полей. Поплавки обрабатываются по-разному в том смысле, что они преобразуются в целочисленные биты с помощью собственной вспомогательной функции, прежде чем накапливаться в хэше. Double, имеющий ту же длину, что и long, преобразуется в long с помощью собственной вспомогательной функции, причем long преобразуется обратно и накапливается в целочисленный результат.

Строки 17-18 выглядят очень по-разному, поскольку они используют некоторый специальный синтаксис и две специально выбранные простые константы, а именно 1231 и 1237. В строке 18 используется тернарный оператор“?:”, который работает аналогично оператору if-else, за исключением того, что это выражение, которое вычисляется как логическое. В этом случае у вас есть myBoolean в качестве условия if, где if true вернет 1231, а else - 1237. Что касается 1231 и 1237, то эти числа выбраны для того, чтобы быть большими простыми числами, которые минимизируют количество хэш-коллизий. Наконец, char-это в основном меньший тип целого числа, поэтому его тривиально накапливать в хэш.

Сравнение

@Override
public boolean equals(Object obj) {
    if (this == obj) {
        return true;
    }
    if (obj == null) {
        return false;
    }
    if (getClass() != obj.getClass()) {
        return false;
    }
    SomeClass other = (SomeClass) obj;
    if (myByte != other.myByte) {
        return false;
    }
    if (myShort != other.myShort) {
        return false;
    }
    if (myInt != other.myInt) {
        return false;
    }
    if (myLong != other.myLong) {
        return false;
    }
    if (Float.floatToIntBits(myFloat) 
            != Float.floatToIntBits(other.myFloat)) {
        return false;
    }
    if (Double.doubleToLongBits(myDouble) 
            != Double.doubleToLongBits(other.myDouble)) {
        return false;
    }
    if (myBoolean != other.myBoolean) {
        return false;
    }
    if (myChar != other.myChar) {
        return false;
    }
    return myString.equals(other.myString);
}

Для примитивных значений мы просто используем оператор равенства. Мы начинаем с наименьших возможных значений, потому что проверка их имеет наибольший шанс ускорить выполнение кода через несколько запусков, то есть мы переходим от byte, к short, к int, к long и так далее. Типы с плавающей запятой немного более сложны для сравнения. float и double должны быть преобразованы в int и long соответственно, прежде чем мы сравним их. булевы тривиальны для сравнения, и мы могли бы поместить их наверх для лучшей производительности.

Тщательный бизнес-анализ может выявить еще более эффективные способы организации этих полей для повышения производительности. Опять же, тесты производительности на реальных данных в конечном счете являются лучшими способами достижения максимально быстрого времени выполнения, когда это необходимо. Конечно, все эти методы оптимизации были бы полезны только в том случае, если бы речь шла о производительности. В противном случае порядок сравнения, вероятно, не имеет значения.
статьи IT, уроки по java, java, хэширование, коллекции