Хэширование – это фундаментальная концепция в программировании.
В Java эффективные алгоритмы хеширования лежат в основе некоторых из самых популярных коллекций, таких как HashMap и HashSet.
Простейшие операции с коллекциями могут быть неэффективными в определенных ситуациях.
Чтобы проиллюстрировать это, запустим линейный поиск, который крайне неэффективен для больших списков:
List<String> list = Arrays.asList("Python", "CSharp", "Kotlin", "Java");
if (list.contains("Java")) {
System.out.println("Строка Java найдена в списке");
}Java предоставляет ряд структур данных специально для решения этой проблемы. Например, несколько реализаций интерфейса Map представляют собой хэш-таблицы (HashTable).
При использовании хэш-таблицы эти коллекции сначала вычисляют хэш-значение для данного ключа с помощью метода hashCode(). Затем это значение используется для хранения данных, чтобы операции доступа были более эффективными.
Как работает hashCode()
Если говорить упрощенно, то hashCode() возвращает целое значение, сгенерированное алгоритмом хеширования. Объекты, которые равны (в соответствии со значением их equals()), должны возвращать один и тот же хэш-код. Разным объектам не обязательно возвращать разные хэш-коды.
Общий контракт hashCode() гласит:
- Всякий раз, когда hashCode() вызывается для одного и того же объекта более одного раза во время выполнения Java-приложения, он должен последовательно возвращать одно и то же значение при условии, что никакая информация, используемая в сравнениях equals() для объекта, не изменяется. Это значение не обязательно должно оставаться неизменным от одного запуска приложения к другому запуску того же приложения.
- Если два объекта равны в соответствии с методом equals(), вызов метода hashCode() для каждого из двух объектов должен выдавать одинаковое значение.
- Если два объекта неравны в соответствии с методом equals(), вызываемый метод hashCode() для каждого из двух объектов, не обязательно должен выдавать различные целочисленные результаты. Однако разработчики должны знать, что получение различных целочисленных результатов для неодинаковых объектов повышает производительность хэш-таблиц.
Простая реализация hashCode()
Наивная реализация hashCode(), которая полностью соответствует приведенному выше контракту, на самом деле довольно проста.
Чтобы продемонстрировать это, мы собираемся определить пример класса, который переопределяет реализацию метода по умолчанию:
public class Person {
private int 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));
}
}Класс Person предоставляет пользовательские реализации как для equals(), так и для hashCode(), которые полностью соответствуют контрактам. Более того, нет ничего незаконного в том, что функция hashCode() возвращает любое фиксированное значение.
Однако эта реализация сводит функциональность хэш-таблиц практически к нулю, поскольку каждый объект будет храниться в одном и том же сегменте.
В этом контексте поиск по хэш-таблице выполняется линейно и не дает нам никакого реального преимущества. Подробнее мы поговорим об этом чуть позже.
Улучшение реализации hashCode()
Давайте модернизируем текущую реализацию hashCode(), включив все поля класса Person, чтобы он мог выдавать разные результаты для неодинаковых объектов:
@Override
public int hashCode() {
return id * email.hashCode() * name.hashCode();
}Этот базовый алгоритм хеширования определенно намного лучше предыдущего. Это связано с тем, что он вычисляет хэш-код объекта путем простого умножения хэш-кодов полей name и email и id.
Мы можем сказать, что это разумная реализация hashCode(), при условии, что мы поддерживаем реализацию equals() в соответствии с ней.
Стандартные реализации hashCode()
Чем лучше алгоритм хеширования, который мы используем для вычисления хэш-кодов, тем выше производительность хэш-таблиц.
Давайте взглянем на стандартную реализацию, которая использует два простых числа для придания еще большей уникальности вычисляемым хэш-кодам:
@Override
public int hashCode() {
int hash = 7;
hash = 31 * hash + 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(email, name)IntelliJ IDEA генерирует следующую реализацию:
@Override
public int hashCode() {
int result = (int) (id ^ (id >>> 32));
result = 31 * result + email.hashCode();
result = 31 * result + name.hashCode();
return result;
}And Eclipse produces this one:
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((email == null) ? 0 : name.hashCode());
result = prime * result + (int) (id ^ (id >>> 32));
result = prime * result + ((name == null) ? 0 : email.hashCode());
return result;
}В дополнение к вышеупомянутым реализациям hashCode() на основе IDE, также возможно автоматически сгенерировать эффективную реализацию, например, с помощью Lombok.
В этом случае нам нужно добавить зависимость lombok-maven к pom.xml:
<dependency>
<groupId>org.projectlombok</groupId>
<artifactId>lombok</artifactId>
<version>1.18.26</version>
<scope>provided</scope>
</dependency>После этого достаточно аннотировать пользовательский класс с помощью @EqualsAndHashCode:
@EqualsAndHashCode
public class Person {
// здесь поля и методы класса...
}Аналогично, если мы хотим, чтобы класс HashCodeBuilder из Apache Commons Lang сгенерировал для нас реализацию hashCode(), мы включаем зависимость commons-lang в файл pom:
<dependency>
<groupId>commons-lang</groupId>
<artifactId>commons-lang</artifactId>
<version>2.7</version>
</dependency>И hashCode() может быть реализован следующим образом:
public class Person {
public int hashCode() {
return new HashCodeBuilder(17, 37).
append(id).
append(email).
append(name).
toHashCode();
}
}В общем, универсального рецепта, когда дело доходит до реализации hashCode(), не существует. Мы настоятельно рекомендуем прочитать книгу Джошуа Блоха “Эффективная Java“. В ней содержится список подробных рекомендаций по реализации эффективных алгоритмов хэширования.
Обратите внимание, что все реализации используют число 31 в той или иной форме. Это связано с тем, что у 31 есть хорошее свойство: его умножение может быть заменено побитовым сдвигом, который выполняется быстрее, чем стандартное умножение
31 * i == (i << 5) - iОбработка коллизий хэшей
Внутреннее устройство хэш-таблиц влечет важный аспект этих структур данных: даже при использовании эффективного алгоритма хеширования два или более объекта могут иметь одинаковый хэш-код, даже если они неодинаковы. Таким образом, их хэш-коды будут указывать на один и тот же bucket, даже если у них будут разные ключи хэш-таблицы.
Эта ситуация широко известна как коллизия хэшей, и для ее решения существуют различные методы, каждый из которых имеет свои плюсы и минусы. HashMap в Java использует отдельный chaining метод для обработки коллизий:
“Когда два или более объекта указывают на один и тот же bucket, они просто сохраняются в связанном списке. В таком случае хэш-таблица представляет собой массив связанных списков, и каждый объект с одинаковым хэшем добавляется к связанному списку по индексу bucket-а в массиве.
В худшем случае к нескольким сегментам был бы привязан связанный список, и извлечение объекта из списка выполнялось бы линейно.”
Поэтому так важно эффективно реализовать hashCode().
Java 8 внесла интересное усовершенствование в реализацию HashMap. Если размер bucket-а превышает определенный порог, связанный список заменяется на TreeMap. Это позволяет добиться скорости поиска O(logn) вместо пессимистичного O(n).
