Что такое хэш код java
Руководство по хэш-коду () на Java
Узнайте, как работает хэш-код и как его правильно реализовать.
1. Обзор
Хэшинг является фундаментальной концепцией информатики.
В этой статье мы сосредоточимся на том, как хэш-код () работает, как он играет в коллекции и как реализовать его правильно.
Дальнейшее чтение:
Java равно () и хэш-код () Контракты
Создание равных () и хэш-кода () с Eclipse
Введение в проект Ломбок
2. Использование хэш-кода () в структурах данных
Простейшие операции по сборам могут быть неэффективными в определенных ситуациях.
Например, это вызывает линейный поиск, который является крайне неэффективным для списков огромных размеров:
Java предоставляет ряд структур данных для решения этой проблемы в частности – например, несколько Карта реализации интерфейса хэш-таблицы.
При использовании хэш-стола эти коллекции вычисляют значение хэша для данного ключа с помощью хэш-код () метод и использовать это значение внутренне для хранения данных, чтобы операции доступа были гораздо более эффективными.
3. Понимание того, как работает хэш-код ()
Проще говоря, хэш-код () возвращает значение integer, генерируемое алгоритмом хэширования.
Объекты, которые равны (в соответствии с их равными () ) должны вернуть тот же хэш-код. Для различных объектов не требуется возвращать различные хэш-коды.
Генеральный контракт хэш-код () Государств:
“Насколько это разумно практично, хэш-код () метод, определяемый классом Объект возвращает различные интеграторы для отдельных объектов. (Обычно это реализуется путем преобразования внутреннего адреса объекта в интегратор, но этот метод реализации не требуется языком программирования JavaTM.)»
4. Наивный хэш-код () Реализация
Это на самом деле довольно просто иметь наивный хэш-код () полностью придерживается вышеупомянутого контракта.
Чтобы продемонстрировать это, мы собираемся определить образец Пользователь класс, переопределяет реализацию метода по умолчанию:
Пользователь класс предоставляет пользовательские реализации для обеих равны () и хэш-код () которые полностью придерживаются соответствующих контрактов. Более того, нет ничего незаконного в том, чтобы хэш-код () возврат любого фиксированного значения.
Однако эта реализация ухудшает функциональность хэш-таблиц практически до нуля, так как каждый объект будет храниться в одном и том же ведре.
В этом контексте поиск хэш-таблицы выполняется линейно и не дает нам реального преимущества – подробнее об этом в разделе 7.
5. Улучшение хэш-кода () Реализация
Давайте немного улучшить текущее хэш-код () реализации путем включения всех областей Пользователь класс, чтобы он может дать различные результаты для неравных объектов:
В общих чертах можно сказать, что это разумный хэш-код () реализации, до тех пор, как мы равны () реализации в соответствии с ним.
6. Стандартный хэш-код () Реализации
Чем лучше алгоритм хэширования, который мы используем для вычисления хэш-кодов, тем лучше будет производительность хэш-таблиц.
Давайте посмотрим на “стандартную” реализацию, которая использует два основных числа, чтобы добавить еще больше уникальности в вычисленные хэш-коды:
Хотя очень важно понимать роли, которые хэш-код () и равны () методы игры, мы не должны осуществлять их с нуля каждый раз, так как большинство IDEs может генерировать пользовательские хэш-код () и равны () реализации и с Java 7, мы получили Объекты.хэш () утилита для удобного хэширования:
IntelliJ IDEA генерирует следующую реализацию:
И Затмение производит этот:
Теперь достаточно аннотировать Пользователь класс с @EqualsAndHashCode :
Точно так же, если мы хотим Апач Викисклад Ланг HashCodeBuilder класс для создания хэш-код () реализации для нас, общий ланг Зависимость Maven должна быть включена в файл pom:
И хэш-код () могут быть реализованы так:
Что можно заметить здесь, что все эти реализации использовать номер 31 в той или иной форме – это потому, что 31 имеет хорошее свойство – его умножение может быть заменено немного сдвиг, который быстрее, чем стандартное умножение:
7. Обработка хэш-столкновений
Внутреннее поведение хэш-таблиц поднимает соответствующий аспект этих структур данных: даже при эффективном алгоритме хэширования два или более объектов могут иметь один и тот же хэш-код, даже если они неравны. Таким образом, их хэш-коды будут указывать на то же ведро, даже если они будут иметь различные хэш-ключи таблицы.
“Когда два или более объектов указывают на одно и то же ведро, они просто хранятся в связанном списке. В этом случае таблица хэша является массивом связанных списков, и каждый объект с одним и тем же хэшом прибвётся к связанному списку индекса ведра в массиве.
Методологии столкновения хэша в двух словах показывают, почему так важно реализовать хэш-код () эффективно .
8. Создание тривиального приложения
Проверить функциональность стандартного хэш-код () реализации, давайте создадим простое java-приложение, которое добавляет некоторые Пользователь объекты для HashMap и использует SLF4J для регистрации сообщения на консоли каждый раз, когда метод называется.
Вот точка входа образца приложения:
И это хэш-код () реализация:
Единственная деталь, которую стоит подчеркнуть здесь, состоит в том, что каждый раз объект хранится на хэш-карте и проверяется с содержитКей () метод, хэш-код () вызывается и вычисляемый хэш-код распечатан на консоли:
9. Заключение
Понятно, что производство эффективных хэш-код () реализация часто требует смешения нескольких математических понятий (т.е. простых и произвольных чисел), логических и базовых математических операций.
Хэш-код объекта, hashCode
Рассмотрим простой пример HashCodeTest.java, который в консоли будет печатать значение hashCode.
Значение hashCode программы можно увидеть в консоли.
По умолчанию, функция hashCode() для объекта возвращает номер ячейки памяти, где объект сохраняется. Поэтому, если изменение в код приложения не вносятся, то функция должна выдавать одно и то же значение. При незначительном изменении кода значение hashCode также изменится.
Функция сравнения объектов equals()
В родительском классе Object наряду с функцией hashCode() имеется еще и логическая функция equals(Object)/ Функция equals(Object) используется для проверки равенства двух объектов. Реализация данной функции по умолчанию просто проверяет по ссылкам два объекта на предмет их эквивалентности.
Рассмотрим пример сравнения двух однотипных объектов Test следующего вида :
Создадим 2 объекта типа Test с одинаковыми значениями и сравним объекты с использованием функции equals().
Результат выполнения программы будет выведен в консоль :
Не трудно было догадаться, что результат сравнения двух объектов вернет «false». На самом деле, это не совсем верно, поскольку объекты идентичны и в real time application метод должен вернуть true. Чтобы достигнуть этого корректного поведения, необходимо переопределить метод equals() объекта Test.
Вот теперь функция сравнения equals() возвращает значение «true». Достаточно ли этого? Попробуем добавить объекты в коллекцию HashSet и посмотрим, сколько объектов будет в коллекции? Для этого в в метод main примера EqualsExample добавим следующие строки :
Однако в коллекции у нас два объекта.
Поскольку Set содержит только уникальные объекты, то внутри HashSet должен быть только один экземпляр. Чтобы этого достичь, объекты должны возвращать одинаковый hashCode. То есть нам необходимо переопределить также функцию hashCode() вместе с equals().
Таким образом, переопределяя методы hashCode() и equals() мы можем корректно управлять нашими объектами, не допуская их дублирования.
Использование библиотеки commons-lang.jar для переопределения hashCode() и equals()
Процесс формирования методов hashCode() и equals() в IDE Eclipse автоматизирован. Для создания данных методов необходимо правой клавишей мыши вызвать контекстное меню класса (кликнуть на классе) и выбрать пункт меню Source (Class >> Source), в результате которого будет открыто следующее окно со списком меню для класса.
Выбираем пункт меню «Generate hachCode() and equals()» и в класс будут добавлены соответствующие методы.
Библиотека Apache Commons включает два вспомогательных класса HashCodeBuilder и EqualsBuilder для вызова методов hashCode() и equals(). Чтобы включить их в класс необходимо внести следующие изменения.
Примечание : желательно в методах hashCode() и equals() не использовать ссылки на поля, заменяйте их геттерами. Это связано с тем, что в некоторых технологиях java поля загружаются при помощи отложенной загрузки (lazy load) и не доступны, пока не вызваны их геттеры.
Скачать пример
Исходный код рассмотренного примера в виде проекта Eclipse можно скачать здесь (263 Kб).
В предыдущей части, если не читали вот она, мы подробно рассмотрели работу метода equals(), его контракт, ошибки и их исправления. Теперь настала очередь второго попугая-неразлучника – метода hashCode().
При переопределении метода equals() мы всегда должны переопределять метод hashCode(). Метод hashCode() – вычисляет целочисленное значение для конкретного элемента класса, чтобы использовать его для быстрого поиска и доступа к этому элементу в hash-структурах данных, например, HashMap, HashSet и прочих. Почему важно переопределять hashCode() всегда вместе с методом equals()? Развернуто ответим на этот вопрос. Пожалуй, необходимо и достаточно знать два важных аспекта, чтобы понять, почему необходимо делать переопределение методов вместе:
Что такое хеш-таблицы (Hash Tables)?
Хэш – таблицы – это своего рода ассоциативный массив, хранящий значения в виде “ключ-значение”. Рассмотрим работу вставки элемента в хеш-таблицу:
На деле все просто, но если еще раз перечитать контракт hashCode() и equals(), то все становиться немного труднее: возможны коллизии – два разных объекта имеют одинаковый hash-код. Что делать? Эта проблема и ее решение отражены на рисунке выше. Два объекта John Smith и Sandra Dee имеют один и тот же hash-код. Для разрешения это коллизии мы просто берем за структуру bucket направленный список. И сохраняем два значения по одному hash-коду.
Как сломать хеш – таблицу?
При неверной реализации метода hashCode() мы можем легко сломать hash-таблицу. Вернее даже сказать не сломать, а сделать ее вырожденной. Например, переопределив метод hashCode() следующим образом
Разбираемся с hashCode() и equals()
Что такое хеш-код?
Если очень просто, то хеш-код — это число. На самом деле просто, не так ли? Если более точно, то это битовая строка фиксированной длины, полученная из массива произвольной длины (википедия).
Пример №1
Выполним следующий код:
Вторая часть объяснения гласит:
полученная из массива произвольной длины.
В итоге, в терминах Java, хеш-код — это целочисленный результат работы метода, которому в качестве входного параметра передан объект.
Подведём итог:
Сперва, что-бы избежать путаницы, определимся с терминологией. Одинаковые объекты — это объекты одного класса с одинаковым содержимым полей.
Понятие эквивалентности. Метод equals()
Начнем с того, что в java, каждый вызов оператора new порождает новый объект в памяти. Для иллюстрации создадим какой-нибудь класс, пускай он будет называться “BlackBox”.
Пример №2
Выполним следующий код:
Во втором примере, в памяти создастся два объекта.
Эквивалентность и хеш-код тесно связанны между собой, поскольку хеш-код вычисляется на основании содержимого объекта (значения полей) и если у двух объектов одного и того же класса содержимое одинаковое, то и хеш-коды должны быть одинаковые (см. правило 2).
Класс Object
При сравнение объектов, операция “ == ” вернет true лишь в одном случае — когда ссылки указывают на один и тот-же объект. В данном случае не учитывается содержимое полей.
Заглянем в исходный код метода hashCode() в классе Object :
При вычислении хэш-кода для объектов класса Object по умолчанию используется Park-Miller RNG алгоритм. В основу работы данного алгоритма положен генератор случайных чисел. Это означает, что при каждом запуске программы у объекта будет разный хэш-код.
Но, как мы помним, должно выполняться правило: “если у двух объектов одного и того же класса содержимое одинаковое, то и хеш-коды должны быть одинаковые ”. Поэтому, при создании пользовательского класса, принято переопределять методы hashCode() и equals() таким образом, что бы учитывались поля объекта.
Это можно сделать вручную либо воспользовавшись средствами генерации исходного кода в IDE. Например, в Eclipse это Source → Generate hashCode() and equals().
В итоге, класс BlackBox приобретает вид:
Теперь методы hashCode() и equals() работают корректно и учитывают содержимое полей объекта:
Кому интересно переопределение в ручную, можно почитать Effective Java — Joshua Bloch, chapter 3, item 8,9.
Заметки о реализации hashCode() в Java
Часто на собеседованиях приходится спрашивать про функцию hashCode().
Я не буду здесь перечислять все свойства этой функции и ее связь с другой, не менее важной функцией equals(). Данная информация есть во всех учебниках по Java и я не вижу смысла ее здесь повторять. Мне бы хотелось остановиться лишь на одном свойстве: hashCode должен быть равномерно распределен на области значений функции. Я задумался: “А чем гарантировано равномерное распределение?”
Забегая вперед, скажу, что я пришел к довольно интересным выводам. Мне бы хотелось, чтобы меня поправили, если я где-то ошибся в рассуждениях.
Спросим у Гуру
Вначале я решил обратиться к Java документации на Object.hashCode(). Как каждый может убедиться, там нет информации, которая нас интересует. После этого я пошел к Гуру. Брюс Эккель написал 5 страниц, кивнул на Блоха (точнее списал у него), привел пример со строками, а в конце посоветовал использовать “полезные библиотеки”. Джошуа Блох поступил лучше: он предложил алгоритм вычисления, высказался о пользе простых чисел и… тоже привел пример. Я не могу не удержаться от цитирования:
The multiplier 37 was chosen because it is an odd prime. … The advantages of using a prime number are less clear, but it is traditional to use primes for this purpose.
Никто из авторов не удосужился провести анализ приведенного алгоритма и доказать его корректность.
Алгоритм (в вольном пересказе)
1) Взять число, отличное от нуля, к примеру 17. Для удобства, назовем его p. Присвоить переменной result это начальное значение (result = p).
2) Для каждого поля вычислить hashCode c по некоторым правилам. Эти правила, нас сейчас не очень интересуют, они не влияют на результат. Для простоты будем работать с целыми числами (int) и будем принимать hashCode равным самому значению числа…
3) Скомбинировать result и полученный hashCode с: result = result * q + c, где q = 37, потому что, как мы помним, оно нечетное и простое.
4) Вернуть result.
Анализ алгоритма
Чтобы быть более конкретным, я стану рассматривать точки с целочисленными координатами (x, y) на плоскости в двухмерном пространстве, при условии, что x>= 0, y>=0.
Запишем hash функцию для точки P1 (x1, y1):
q(x1-x2) + y1 — y2 = 0 (Обратите внимание, что множитель, содержащий p пропал после вычитания)
(x1 — x2) / (y2-y1) = q (понятно, что знаменатель должен быть отличен от нуля)
Если подобрать такие значения x1, x2, y1, y2, что выполнится полученное равенство, то эти координаты будут соответствовать значениям аргумента hash функции, при которой возникнет коллизия.
Можно предложить такой вариант:
То есть точки P(38, 1) и P(1, 2) имеют одинаковый hashCode… Я думал, что имея 4 миллиарда возможных значений для hash кода, можно было бы избежать коллизий хотя бы в квадрате 100×100!
Теперь рассмотрим случай n переменных, независимо изменяющихся от 0 до некоторого M. Хотелось бы найти максимальное значение M, такое, что хорошо написанная функция hashCode не имела бы коллизий на промежутке от 0 до M по всем n переменным. После недолгих раздумий, получаем значение для M:
Для случая точек на плоскости M принимает значение 65536.
Похоже, что формула, приведенная Блохом, будет давать приемлемое распределение hash кодов для случая 8 и более переменных.
Рассмотрим теперь точки в трехмерном пространстве. Напишем небольшую программу, которая в тройном цикле перебирает точки от 0 до 100 (всего миллион точек) и считает количество коллизий. Код этой программы элементарный, поэтому не буду его здесь приводить. Интересен результат: я получил 901692 коллизий! То есть чуть более, чем 90%. Получается, что Блох, под видом hash функции, предложил функцию для получения коллизий?
Хороший hashCode для случая двух переменных
p*(x1-x2) + q(y1-y2) = 0
или
(x1-x2)/(y2-y1)=q/p (при условии, что знаменатель не равен нулю)
Выводы
Как писал Дональд Кнут в главе про генератор псевдослучайных последовательностей, если алгоритм выглядит сложно и запутанно, это еще не означает, что он работает правильно (недословное изложение).
Те кто используют реализацию hash функции от Джошуа Блоха, но имеют большое количество хешируемых переменных, могут спать спокойно. Так же могут не волноваться те, у кого различного рода Hash-коллекции не являются узким местом в производительности.
Если же вы бьетесь за производительность своего кода, учитываете все возможные мелочи, то вам, пожалуй, следует взглянуть на свои реализации hashCode() свежим взглядом. Учитывая, что хешируемые значения, могут быть не равномерно распределены для вашей конкретной бизнес области, вы сможете написать hash функцию с лучшим распределением hash кодов, чем любой сгенерированный вариант. Переписав hashCode(), вам, возможно, следует взглянуть на equals(): может быть вы сможете меньшим числом проверок вернуть значение false.
Спасибо тем, кто дочитал до конца.
Литература:
Bruce Eckel “Thinking in Java Third Edition”
Joshua Bloch “Effective Java: Programming Language Guide”