Что такое хэш-код

Обновлено: 22.11.2024

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

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

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

Дополнительная литература:

Контракты Java equals() и hashCode()

Узнайте о контрактах, которые должны выполнять equals() и hasCode(), и о связи между этими двумя методами

Сгенерировать equals() и hashCode() с помощью Eclipse

Введение в проект Ломбок

Всеобъемлющее и очень практичное введение во многие полезные варианты использования Project Lombok в стандартном коде Java.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

И Eclipse производит вот это:

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

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

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

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

И hashCode() можно реализовать следующим образом:

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

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

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

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

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

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

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

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

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

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

Теперь мы проверим функциональность стандартной реализации hashCode().

Давайте создадим простое Java-приложение, которое добавляет несколько объектов User в HashMap и использует SLF4J для вывода сообщения на консоль при каждом вызове метода.

Вот точка входа примера приложения:

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

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

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

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

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

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

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

Дополнительная литература:

Контракты Java equals() и hashCode()

Узнайте о контрактах, которые должны выполнять equals() и hasCode(), и о связи между этими двумя методами

Сгенерировать equals() и hashCode() с помощью Eclipse

Введение в проект Ломбок

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

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

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

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

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

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

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

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

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

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

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

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

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

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

И Eclipse производит вот это:

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

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

И hashCode() можно реализовать следующим образом:

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

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

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

Теперь мы проверим функциональность стандартной реализации hashCode().

Вот точка входа примера приложения:

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

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

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

Хеширование предназначено для решения проблемы эффективного поиска или сохранения элемента в коллекции.

Например, если у нас есть список из 10 000 слов английского языка, и мы хотим проверить, есть ли данное слово в списке, было бы неэффективно последовательно сравнивать слово со всеми 10 000 элементов, пока мы не найдем совпадение. Даже если список слов отсортирован лексикографически, как в словаре, вам все равно потребуется некоторое время, чтобы найти искомое слово.

Хеширование – это метод повышения эффективности за счет сужения области поиска с самого начала.

Что такое хеширование?

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

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

Как правило, эти хэш-коды используются для создания индекса, в котором хранится значение.

Как работает хеширование

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

Хеш-таблицы должны поддерживать 3 функции.

вставить (ключ, значение)
получить (ключ)
удалить (ключ)

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

Допустим, мы хотим сохранить данные таблицы на карте.

Предположим, наша хеш-функция просто берет длину строки.

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

Например, хэш-код (длина) Кубы равен 4. Таким образом, мы сохраняем Кубу на 4-й позиции в массиве ключей, а Гавану — на 4-м индексе массива значений и т. д. В результате мы получаем следующее:

Теперь в этом конкретном примере все работает достаточно хорошо. Наш массив должен быть достаточно большим, чтобы вместить самую длинную строку, но в данном случае это всего 11 слотов.
Мы тратим немного места, потому что, например, в наших данных нет однобуквенных ключей, а также клавиши от 8 до 10 букв.

Но и в этом случае пустое пространство не так уж и плохо. Получение длины строки — это удобно и быстро, как и процесс нахождения значения, связанного с заданным ключом (конечно, быстрее, чем сравнение до пяти строк).

Но что нам делать, если в нашем наборе данных есть строка из более чем 11 символов?
Что, если у нас есть еще одно слово из 5 символов, «Индия», и мы пытаемся присвоить его индексу, используя наш хэш-функция. Поскольку индекс 5 уже занят, мы должны сделать вызов, что с ним делать. Это называется коллизией.

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

Обработка конфликтов

Для обработки коллизий используются два основных метода.

Отдельная цепочка

Обработка коллизий хэшей с помощью отдельной цепочки использует дополнительную структуру данных, предпочтительно связанный список для динамического распределения в сегментах. В нашем примере, когда мы добавляем Индию в набор данных, она добавляется к связанному списку, хранящемуся в индексе 5, тогда наша таблица будет выглядеть так.

Чтобы найти элемент, мы сначала идем в корзину, а затем сравниваем ключи. Это популярный метод, и если используется список ссылок, хэш никогда не заполняется. Стоимость get(k) в среднем составляет O(n), где n — количество ключей в корзине, общее количество ключей равно N.

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

Сегодня в этом уроке мы познакомим вас с одним из фундаментальных понятий компьютерных наук — «хешированием» в Java. Мы реализуем хеширование с помощью функции hashCode в Java.

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

Чтобы лучше понять это, посмотрите на следующий сценарий –

Есть трое друзей — Рахул, Рави и Сэм, которые учатся в одной школе.
Рави и Сэм относятся к направлению "Наука", а Рахул относится к направлению "Коммерция". Таким образом, технически код класса Рави и Сэма будет одинаковым, а код Рахула будет другим, хотя все они учатся в 10-м классе, то есть в одном классе.
Теперь к ним в класс пришла новая учительница. Она хочет знать каталожные номера Рави и Сэма. Поэтому, когда она введет их соответствующие имена в базу данных учащихся, она обнаружит, что их номера в списках уникальны.
Затем она решает сравнить номер Рахула в базе данных учащихся и в Журнале посещаемости. Она считает, что это то же самое.
Концепция hashCode в Java примерно такая. Если два объекта равны, то их хэш-код будет идентичным. Однако обратное не всегда верно.Если есть два разных объекта в двух разных местах памяти, у них будут совершенно разные хэш-коды.

Метод hashCode() в Java

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

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

В алгоритме хэширования метод hashCode сопоставляет некоторые ключи с их значениями. Значения хранятся в определенных местах памяти с использованием доступных структур хеш-данных, таких как HashMap, HashSet и HashTable. Затем они извлекаются с использованием указанных ключей для различных операций, которые нам могут понадобиться.

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

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

Типы функций hashCode в Java

hashCode в Java бывает двух типов в зависимости от соответствующих параметров:

Метод hashCode(). Метод hashCode принадлежит классу Java Integer. Этот метод переопределяет хэш-код класса Object.
Метод hashCode(int value) — метод hashCode(int value), явно имеющий параметр, определяет хэш-код заданного значения параметра int.

Синтаксис hashCode в Java

Синтаксис двух типов hashCode в Java следующий:

Параметры метода hashCode

Как мы видим, первый тип метода hashCode не имеет параметра.

Второй тип метода hashCode имеет следующий параметр:

Тип данных	Параметр	Описание
int	value	Это «значение» определяет хэш-код.

Возвращаемое значение метода hashCode в Java

Возвращаемое значение двух типов метода hashCode в Java выглядит следующим образом:

< tbody>

Метод	Возвращаемое значение
hashCode()	Этот метод возвращает хэш-код текущего объекта, равный примитивное значение int.
hashCode(int value)	Это метод возвращает хэш-код для целочисленного «значения», переданного через функцию.

Реализация hashCode в Java

Теперь, когда мы закончили изучение различных типов hashCode в Java, их синтаксиса и параметров, давайте напишем код!

Сначала мы будем работать с двумя одинаковыми объектами, а затем с двумя неравными.
Ожидаемый результат состоит в том, что неравные будут иметь разные хэш-коды.
Один и тот же код будет иметь одинаковый хеш-код.
Мы также попытаемся найти хэш-код строки «Изучение хэш-кода в Java».
Взгляните на следующий код –

Теперь давайте посмотрим, как получить хэш-код в Java, передав параметр методу –

Для наших продвинутых учеников мы можем посмотреть, как hashCode в Java реализуется с помощью HashMaps.

HashMap является частью коллекций в Java.
Полученное значение хэш-кода называется номером корзины.
Массив узлов называется сегментом.

Взгляните на следующий пример, чтобы понять его реализацию –

Теперь, если мы хотим рассчитать индекс какой-либо одной записи, например, «Сэм», мы используем следующую формулу —