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

1. Обзор

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

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

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

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

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

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

List words = Arrays.asList("Welcome", "to", "Baeldung"); if (words.contains("Baeldung")) { System.out.println("Baeldung 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 (), которая полностью соответствует вышеуказанному контракту.

Чтобы продемонстрировать это, мы собираемся определить образец класса 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 () , включив все поля класса User, чтобы он мог давать разные результаты для неравных объектов:

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

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

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

6. Стандартный хэш - код () Реализации

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

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

@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. В этом случае, Ломбок-Maven зависимость должна быть добавлена к pom.xml :

 org.projectlombok lombok-maven 1.16.18.0 pom 

It's now enough to annotate the User class with @EqualsAndHashCode:

@EqualsAndHashCode public class User { // fields and methods here }

Similarly, if we want Apache Commons Lang's HashCodeBuilder class to generate a hashCode() implementation for us, the commons-lang Maven dependency must be included in the pom file:

 commons-lang commons-lang 2.6 

And hashCode() can be implemented like this:

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

In general, there's no universal recipe to stick to when it comes to implementing hashCode(). We highly recommend reading Joshua Bloch's Effective Java, which provides a list of thorough guidelines for implementing efficient hashing algorithms.

What can be noticed here is that all those implementations utilize number 31 in some form – this is because 31 has a nice property – its multiplication can be replaced by a bitwise shift which is faster than the standard multiplication:

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

7. Handling Hash Collisions

The intrinsic behavior of hash tables raises up a relevant aspect of these data structures: even with an efficient hashing algorithm, two or more objects might have the same hash code, even if they're unequal. So, their hash codes would point to the same bucket, even though they would have different hash table keys.

This situation is commonly known as a hash collision, and various methodologies exist for handling it, with each one having their pros and cons. Java's HashMap uses the separate chaining method for handling collisions:

“When two or more objects point to the same bucket, they're simply stored in a linked list. In such a case, the hash table is an array of linked lists, and each object with the same hash is appended to the linked list at the bucket index in the array.

In the worst case, several buckets would have a linked list bound to it, and the retrieval of an object in the list would be performed linearly.”

Hash collision methodologies show in a nutshell why it's so important to implement hashCode() efficiently.

Java 8 brought an interesting enhancement to HashMap implementation – if a bucket size goes beyond the certain threshold, the linked list gets replaced with a tree map. This allows achieving O(logn) look up instead of pessimistic O(n).

8. Creating a Trivial Application

To test the functionality of a standard hashCode() implementation, let's create a simple Java application that adds some User objects to a HashMap and uses SLF4J for logging a message to the console each time the method is called.

Here's the sample application's entry point:

public class Application { public static void main(String[] args) { Map users = new HashMap(); User user1 = new User(1L, "John", "[email protected]"); User user2 = new User(2L, "Jennifer", "[email protected]"); User user3 = new User(3L, "Mary", "[email protected]"); users.put(user1, user1); users.put(user2, user2); users.put(user3, user3); if (users.containsKey(user1)) { System.out.print("User found in the collection"); } } } 

And this is the hashCode() implementation:

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; } }

The only detail worth stressing here is that each time an object is stored in the hash map and checked with the containsKey() method, hashCode() is invoked and the computed hash code is printed out to the console:

[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

9. Conclusion

It's clear that producing efficient hashCode() implementations often requires a mixture of a few mathematical concepts, (i.e. prime and arbitrary numbers), logical and basic mathematical operations.

Regardless, it's entirely possible to implement hashCode() effectively without resorting to these techniques at all, as long as we make sure the hashing algorithm produces different hash codes for unequal objects and is consistent with the implementation of equals().

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