Руководство по hashCode() в Java

Хеширование является фундаментальной концепцией информатики.

В Java эффективные алгоритмы хеширования стоят за некоторыми из самых популярных коллекций, таких как HashMap (ознакомьтесь с этой подробной статьей) и HashSet.

В этой статье рассмотрим, как работает hashCode(), как он работает с коллекциями и как его правильно реализовать.

Использование hashCode() в структурах данных

Простейшие операции над коллекциями могут оказаться неэффективными в определенных ситуациях. Для иллюстрации этого запустим линейный поиск, который крайне неэффективен для огромных списков:

List<String> words = Arrays.asList("Welcome", "to", "Baeldung");
if (words.contains("Baeldung")) {
    System.out.println("Baeldung is in the list");
}

Java предоставляет ряд структур данных специально для решения этой проблемы. Например, несколько реализаций интерфейса Map представляют собой хеш-таблицы.

При использовании хеш-таблицы коллекции вычисляют хеш-значение для заданного ключа с помощью метода hashCode(). Затем они используют это значение для внутреннего хранения данных, чтобы операции доступа были более эффективными.

Понимание того, как работает hashCode()

Проще говоря, hashCode() возвращает целочисленное значение, сгенерированное алгоритмом хеширования.

Объекты, которые равны (согласно их equals()), должны возвращать один и тот же хэш-код. Разные объекты не должны возвращать разные хэш-коды. Общий контракт hashCode() гласит:

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

«Насколько это целесообразно, метод hashCode(), определенный классом Object, действительно возвращает разные целые числа для разных объектов. (Обычно это реализуется путем преобразования внутреннего адреса объекта в целое число, но этот метод реализации не требуется языком программирования JavaTM.)»

Нативная реализация hashCode()

Нативная реализация hashCode(), которая полностью соответствует приведенному выше контракту, на самом деле довольно проста. Чтобы продемонстрировать это, определим пример класса User, который переопределяет реализацию метода по умолчанию:

public class User {

    private long id;
    private String name;
    private String email;

    // стандартные геттеры/сеттеры/конструкторы
        
    @Override
    public int hashCode() {
        return 1;
    }
        
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null) return false;
        if (this.getClass() != o.getClass()) return false;
        User user = (User) o;
        return id == user.id 
          && (name.equals(user.name) 
          && email.equals(user.email));
    }
    
    // здесь геттеры и сеттеры
}

Класс User предоставляет пользовательские реализации для equals() и hashCode(), которые полностью соответствуют соответствующим контрактам. Более того, нет ничего страшного в том, что hashCode() возвращает любое фиксированное значение.

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

В этом контексте поиск в хэш-таблице выполняется линейно и не дает никаких реальных преимуществ. Подробнее об этом мы поговорим в разделе 7.

Улучшение реализации hashCode()

Давайте улучшим текущую реализацию hashCode(), включив все поля класса User, чтобы он мог давать разные результаты для неравных объектов:

@Override
public int hashCode() {
    return (int) id * name.hashCode() * email.hashCode();
}

Этот базовый алгоритм хеширования однозначно намного лучше предыдущего. Это связано с тем, что он вычисляет хэш-код объекта, просто умножая хэш-коды полей name, email и id.

В общих чертах, можно сказать, что это разумная реализация hashCode(), пока мы поддерживаем реализацию equals() в соответствии с ней.

Стандартные реализации hashCode()

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

@Override
public int hashCode() {
    int hash = 7;
    hash = 31 * hash + (int) id;
    hash = 31 * hash + (name == null ? 0 : name.hashCode());
    hash = 31 * hash + (email == null ? 0 : email.hashCode());
    return hash;
}

Хотя необходимо понимать роли, которые играют методы hashCode() и equals(), нам не нужно каждый раз реализовывать их с нуля. Это связано с тем, что большинство IDE могут генерировать собственные реализации hashCode() и equals(). А начиная с Java 7 есть служебный метод Objects.hash() для удобного хеширования:

Objects.hash(name, email)

IntelliJ IDEA генерирует следующую реализацию:

@Override
public int hashCode() {
    int result = (int) (id ^ (id >>> 32));
    result = 31 * result + name.hashCode();
    result = 31 * result + email.hashCode();
    return result;
}

А Eclipse генерирует такую реализацию:

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((email == null) ? 0 : email.hashCode());
    result = prime * result + (int) (id ^ (id >>> 32));
    result = prime * result + ((name == null) ? 0 : name.hashCode());
    return result;
}

Помимо описанных выше реализаций hashCode() на основе IDE, также можно автоматически сгенерировать эффективную реализацию, например, с помощью Lombok.

В этом случае необходимо добавить зависимость lombok-maven к pom.xml:

<dependency>
    <groupId>org.projectlombok</groupId>
    <artifactId>lombok-maven</artifactId>
    <version>1.16.18.0</version>
    <type>pom</type>
</dependency>

Теперь достаточно аннотировать класс User с помощью @EqualsAndHashCode:

@EqualsAndHashCode 
public class User {
    // здесь поля и методы
}

Точно так же, если хотим, чтобы класс Apache Commons Lang HashCodeBuilder сгенерировал для нас реализацию hashCode(), то включаем зависимость Maven commons-lang в файл pom:

<dependency>
    <groupId>commons-lang</groupId>
    <artifactId>commons-lang</artifactId>
    <version>2.6</version>
</dependency>

А hashCode() можно реализовать так:

public class User {
    public int hashCode() {
        return new HashCodeBuilder(17, 37).
        append(id).
        append(name).
        append(email).
        toHashCode();
    }
}

В общем, универсального рецепта реализации hashCode() не существует. Настоятельно рекомендуем прочитать книгу Джошуа Блоха «Эффективная Java». Она предоставляет список подробных рекомендаций по реализации эффективных алгоритмов хеширования. Обратите внимание, что все эти реализации используют число 31 в той или иной форме. Это потому, что 31 имеет хорошее свойство. Его умножение можно заменить побитовым сдвигом, который быстрее стандартного умножения:

31 * i == (i << 5) - i

Обработка коллизий хэшей

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

Эта ситуация широко известна как коллизия хэшей, и существуют различные методы ее обработки, каждый из которых имеет свои плюсы и минусы. HashMap в Java использует отдельный метод цепочки для обработки коллизий:

«Когда два или более объекта указывают на одну и ту же корзину, они просто сохраняются в связанном списке. В таком случае хеш-таблица представляет собой массив связанных списков, и каждый объект с одним и тем же хешем добавляется к связанному списку по индексу корзины в массиве.

В худшем случае к нескольким корзинам будет привязан связанный список, и поиск объекта в списке будет выполняться линейно».

Методологии коллизии хэшей в двух словах показывают, почему так важно эффективно реализовать функцию hashCode().

Java 8 привнесла интересное усовершенствование в реализацию HashMap. Если размер корзины превышает определенный порог, связанный список перерождается в красно-черное дерево. Это позволяет достичь поиска O(logn) вместо пессимистического O(n).

Создание простого приложения

Теперь проверим функциональность стандартной реализации hashCode(). Давайте создадим простое Java-приложение, которое добавляет некоторые объекты User в HashMap и использует SLF4J для вывода сообщения в консоль при каждом вызове метода. Вот точка входа примера приложения:

public class Application {

    public static void main(String[] args) {
        Map<User, User> users = new HashMap<>();
        User user1 = new User(1L, "John", "john@domain.com");
        User user2 = new User(2L, "Jennifer", "jennifer@domain.com");
        User user3 = new User(3L, "Mary", "mary@domain.com");

        users.put(user1, user1);
        users.put(user2, user2);
        users.put(user3, user3);
        if (users.containsKey(user1)) {
            System.out.print("User found in the collection");
        }
    }
}

А это реализация hashCode():

public class User {

    // ...

    public int hashCode() {
        int hash = 7;
        hash = 31 * hash + (int) id;
        hash = 31 * hash + (name == null ? 0 : name.hashCode());
        hash = 31 * hash + (email == null ? 0 : email.hashCode());
        logger.info("hashCode() called - Computed hash: " + hash);
        return hash;
    }
}

Здесь важно отметить, что каждый раз, когда объект сохраняется в hashMap и проверяется с помощью метода containsKey(), вызывается функция hashCode(), и вычисленный хэш-код выводится на консоль:

[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: 1255477819
[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: -282948472
[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: -1540702691
[main] INFO com.baeldung.entities.User - hashCode() called - Computed hash: 1255477819
User found in the collection

Заключение

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

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

Примеры кода, показанные в этой статье, доступны на GitHub.

Оригинал

➜