В Java некоторые встроенные библиотеки зависят от реализованного метода хеш-кода объекта. Например, HashMap и HashSet зависят от значения, возвращаемого этим методом. Обеспечение правильной реализации hashCode НЕОБХОДИМО не только для эффективной работы этих структур данных, но и для того, чтобы они могли эффективно обрабатывать эти объекты. В этой статье мы собираемся изучить общий контракт правильной реализации hashCode, когда важно его реализовать, как написать современный код и некоторые приемы для оптимизации его производительности.

Связь между equals и hashCode

Когда метод equals() переопределяется в классе, важно также предоставить реализацию метода hashCode(), чтобы обеспечить правильное функционирование класса в коллекциях, которые полагаются на хэш-коды, такие как HashMap и HashSet. Помните, что важно включить каждое значимое поле в вычисление хэш-кода для класса, который задействован в методе equals(). Думайте о них так, как будто они являются отражением друг друга. Для класса, который выполняет итерацию массива для проверки на равенство, реализация метода hashCode() также должна выполнять итерацию по тому же массиву для вычисления хэш-кода для каждого элемента. Вы можете проверить мой пост о реализации метода equals, чтобы убедиться, что эти два метода работают надежно.

Общий контракт реализации Object.hashCode()

  • Если метод hashCode() вызывается для объекта несколько раз во время выполнения приложения, он всегда должен возвращать одно и то же значение, если никакая информация, используемая в сравнениях equals(), не была изменена.
  • Если два объекта равны в соответствии с их методом equals(Object), то вызов их методов hashCode должен дать одинаковый результат.
  • Для неравных объектов лучше иметь разные хэш-коды. В далеком от идеала мире два неравных объекта могут иметь одинаковый хеш-код.

Равные объекты должны иметь одинаковые хэш-коды. Нарушение этого правила приведет к неожиданному поведению коллекции, подобной HashMap. Давайте посмотрим на пример поведения HashMap в результате нарушения второй части контракта. Предположим, что Person.hashCode() имеет неправильную реализацию, которая дает разные результаты для одинаковых объектов.

/* Example of HashMap behaviour as result of 
   violation of the second part of the contract */
Map<Person, Integer> map = new HashMap<>();

Person p1 = new Person("Name", 20);
Person p2 = new Person("Name", 20);

p1.equals(p2); // true

map.put(p1, 800);
map.get(p2); // Is null

Мы можем предположить, что p1.hashCode() возвращает 10, а p2.hashCode() возвращает 100. Вызов map.put(p1, 800) вставляет p1 в сегмент, соответствующий его хэш-коду, который равен 10. С другой стороны, вызов map.get(p2) пытается найти p2 в сегменте, который соответствует его хеш-коду, равному 100. Очевидно, что он вернет значение null, поскольку его там нет. Вот что будет при нарушении второй части договора. Когда одинаковые объекты, основанные на реализации метода equals, имеют разные хеш-коды, любая коллекция или клиентский код, которые полагаются на это хеш-значение, будут вести себя неправильно.

При написании функции hashCode мы стремимся выполнить два основных требования. Во-первых, объекты, которые считаются равными, должны создавать одинаковый хэш-код. Кроме того, хорошая хеш-функция имеет тенденцию давать разные результаты для разных объектов. Во-вторых, хэш-функция лучше генерирует хэш-коды, равномерно распределенные среди конечного диапазона значений. Это уменьшает количество коллизий во время вставки в структуры данных на основе хэшей. Если все объекты имеют одинаковый хэш, это означает, что такая структура данных, как HashMap, будет вести себя как LinkedList, поскольку она обрабатывает коллизии с помощью концепции, называемой раздельная цепочка. В реальном мире предотвращение коллизий почти невозможно, но мы могли бы добиться лучших результатов при хорошей реализации метода hashCode.

Как достичь справедливого приближения для решения без столкновений

  1. Вычислите hashCode для первого значимого поля «A» и сохраните его в переменной (предположим, что ее имя — hashResult).
  • Если «A» является примитивным типом, вызовите его метод hashCode класса-оболочки.
  • Вызовите A.hashCode(), если это ссылка на объект. Если объект имеет значение null, вы можете заменить его любым постоянным значением, но чаще всего используется ноль.
  • Если это массив, мы рассматриваем каждую запись как значимый объект. Итак, перебираем массив и накапливаем каждый хеш-код в hashResult.

2. Для остальных значимых полей вызываем их метод hashCode и суммируем его с ранее рассчитанным hashResult * 31

Выбор числа 31, потому что это простое число и его легко вычислить с помощью оператора сдвига, который намного быстрее, чем обычное умножение.

Пример лучше иллюстрирует эти шаги.

class Employee {
	private int age;
	private int salary;
	private String name;

	private int hashResult;

	public Employee(int age, int salary, String name) {
		this.age = age;
		this.salary = salary;
                this.name = name;
	}

	@Override
	public int hashCode() {
		hashResult = Integer.hashCode(age);
		hashResult = 31 * hashResult + Integer.hashCode(salary);
		hashResult = 31 * hashResult + (name == null ? 0 
                    : name.hashCode());

		return hashResult;
	}
}

Здесь метод equals исключен, чтобы сократить код, но он должен использовать эти поля для своего результата, в данном случае возраст, зарплата и имя. сильный>. Если объект содержит какое-либо производное поле (поле, значение которого получается из одного или нескольких полей), например, целочисленное поле дни вычисляется из начала и конца даты, он не должен участвовать в вычислении хэш-кода, если значения, используемые для его получения, уже использовались в вычислении. В этом случае мы можем исключить поле дни, если в вычислении хэш-кода участвуют даты начала и конца.

Умножение hashResult каждый раз на 31 дает очень надежный результат, который зависит от порядка полей. Таким образом, если два класса имеют одинаковые значения для разных полей, результат будет разным для обоих. В нашем примере, если у сотрудника e1 возраст = 30, зарплата = 50, а у другого сотрудника e2 возраст = 50,
зарплата = 30, hashResult будет разным для каждого из них.

Совет по повышению производительности. Лучше оптимизировать умножение, используя в коде оператор сдвига. Итак, hashResult * 31 == (hashResult << 5) - hashResult) верно. Известно, что оператор сдвига работает быстрее, чем обычная операция умножения.

Создание собственного хэш-кода или использование встроенного метода Java (Совет по производительности)

Класс Java Object содержит реализацию, которая выглядит почти так же, как наша, Object.hash(Object... values). Хотя он выполняет все необходимые нам вычисления, у него есть недостаток, который должен помешать нам его использовать. Метод hash принимает переменное количество аргументов типа объекта, что приводит к созданию массива для хранения этих объектов, а также процесса их упаковки и распаковки. Это может привести к снижению производительности, если вы используете много полей в вычислении хэш-кода, а метод hashCode вызывается несколько раз. Так что лучше создать свой собственный, используя те же шаги, которые мы упоминали.

Кэшируйте результат хеширования для неизменяемых классов (Совет по производительности)

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

// Immutable class
class Point {
    private final int x;
    private final int y;
    private int hashResult; 

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int hashCode() {
        int result = hashResult;
        
        if(result == 0){
            result = Integer.hashCode(x);
            result = 31 * result + Integer.hashCode(y);
            
            hashResult = result;
        }
        return hashResult;
    }
}

Чтобы свести к минимуму коллизии и повысить производительность HashMap, крайне важно включить высокозначимые поля, даже если это происходит за счет производительности метода hashCode. Включение этих полей помогает избежать ситуаций, когда несколько объектов сопоставляются с одними и теми же хэш-кодами, что может привести к тому, что HashMap будет вести себя как несколько LinkedList и привести к квадратичной временной сложности вместо линейной. Рекомендуется сосредоточиться на использовании полей с большей вероятностью уникальности, таких как идентификатор сотрудника, который не может быть одинаковым для двух разных сотрудников.

Заключение

Вам необходимо написать хеш-функцию, которая выдает одинаковые хэш-коды для одинаковых объектов и максимально разные результаты для неравных объектов. Используйте те же поля, что и в методе equals объекта. Не полагайтесь на Objects.hash(Object... values), потому что это немного плохо повлияет на вашу производительность и использование памяти. Не забудьте кэшировать хэш-код для неизменяемых объектов, если они вызываются несколько раз. Чтобы добиться более равномерного распределения хэш-кодов, рекомендуется выбирать наиболее значимые поля, которые вряд ли будут иметь одинаковые значения, и использовать их для вычисления хэш-кода.

Спасибо за чтение! Если вас интересуют передовые методы написания кода на Java, советы по оптимизации производительности и другие темы Backend Engineering, подписывайтесь на меня и подписывайтесь на мою рассылку, чтобы быть в курсе последних статей.