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

1. Обзор

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

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

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

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

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

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

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

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

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

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

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

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

Общий контракт hashCode() гласит:

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

• Если два объекта равны в соответствии с методом equals(Object) , вызов метода hashCode() для каждого из двух объектов должен дать одно и то же значение.

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

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

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

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

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

public class User {

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

    // standard getters/setters/constructors
        
    @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));
    }
    
    // getters and setters here
}

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

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

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

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

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

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

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

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

6. Стандартные реализации 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 {
    // fields and methods here
}

Точно так же, если мы хотим , чтобы класс 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

7. Обработка конфликтов хэшей

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

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

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

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

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

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

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

Теперь мы проверим функциональность стандартной реализации 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;
    }
}

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

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

9. Заключение

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

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

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