В SitePoint мы всегда стремимся расширить круг обсуждаемых тем. В последнее время мы нацелены на изучение мира Java. Если вы сильный Java-разработчик, который хочет внести свой вклад в наше освещение, свяжитесь с несколькими идеями для статей, которые вы хотели бы написать.
Итак, вы решили, что идентичности вам недостаточно, и написали хорошую реализацию equals ?
Большой! Но теперь вы должны также реализовать hashCode
Посмотрим почему и как это сделать правильно.
Равенство и хэш-код
Хотя равенство имеет смысл с общей точки зрения, хеш-коды являются гораздо более техническими. Если бы мы немного усердно с ними работали, мы могли бы сказать, что это всего лишь деталь реализации для повышения производительности.
Большинство структур данных используют equals Например:
List<String> list = Arrays.asList("a", "b", "c");
boolean contains = list.contains("b");
Переменная containstrue"b"интернирование строк ), они равны.
Однако сравнивать каждый элемент с экземпляром, contains Вместо того, чтобы сравнивать запрошенный экземпляр с каждым элементом, который они содержат, они используют ярлык, который уменьшает количество потенциально равных экземпляров, а затем только сравнивает их.
Этот ярлык является хеш-кодом, который можно рассматривать как равенство объекта, сводимое к целочисленному значению. Экземпляры с одинаковым хеш-кодом не обязательно равны, но равные экземпляры имеют одинаковый хеш-код. (Или должно быть, мы обсудим это в ближайшее время.) Такие структуры данных часто называют в честь этого метода, узнаваемого по HashHashMap
Вот как они обычно работают:
- Когда элемент добавляется, его хеш-код используется для вычисления индекса во внутреннем массиве (называемом сегментом).
- Если другие неравные элементы имеют одинаковый хеш-код, они попадают в один и тот же сегмент и должны быть объединены вместе, например, путем добавления их в список.
- Когда экземпляр передается в
containsТолько элементы в нем сравниваются с экземпляром.
Таким образом, очень немногие, в идеале, сравнения не требуется для реализации equals
На containsequalshashCode
Мысли о хешировании
Если Object
Вот почему, если мы переопределяем hashCodeequals В противном случае вещи, которые равны в соответствии с нашей реализацией, скорее всего, не будут иметь одинаковый хэш-код, потому что они используют реализацию hashCode
Контракт Object
Цитирую источник :
Генеральный договор
hashCode
- Всякий раз, когда он вызывается для одного и того же объекта более одного раза во время выполнения приложения Java, метод
hashCodeЭто целое число не обязательно должно быть согласованным от одного выполнения приложения к другому выполнению того же приложения.- Если два объекта равны в соответствии с методом
hashCodeequals(Object)- Не требуется, чтобы, если два объекта были неравны в соответствии с методом
hashCodeequals(Object)Тем не менее, программист должен знать, что выдача различных целочисленных результатов для неравных объектов может повысить производительность хеш-таблиц.
Первая пуля отражает свойство согласованности hashCode Третий излагает важную деталь, о которой мы поговорим чуть позже.
Реализация equals
Очень простая реализация hashCode
Person.hashCode
Хеш-код человека вычисляется путем вычисления хеш-кодов для соответствующих полей и их объединения. И то, и другое оставлено для @Override
public int hashCode() {
return Objects.hash(firstName, lastName);
}
Objects
Выбор полей
Но какие поля актуальны? Требования помогают ответить на этот вопрос: если равные объекты должны иметь одинаковый хеш-код, то вычисление хеш-кода не должно включать в себя поля, которые не используются для проверок на равенство. (В противном случае два объекта, которые отличаются только в этих полях, будут равны, но имеют разные хеш-коды.)
Таким образом, набор полей, используемых для хеширования, должен быть подмножеством полей, используемых для равенства. По умолчанию оба будут использовать одни и те же поля, но необходимо учитывать несколько деталей.
консистенция
Во-первых, есть требование согласованности. Это следует интерпретировать довольно строго. Хотя он позволяет изменять хэш-код при изменении некоторых полей (что часто является неизбежным для изменяемых классов), структуры хэширования данных не подготовлены для этого сценария.
Как мы видели выше, хеш-код используется для определения корзины элемента. Но если изменяются поля, относящиеся к хешу, хеш не пересчитывается и внутренний массив не обновляется.
Это означает, что более поздний запрос с одинаковым объектом или даже с тем же экземпляром завершится неудачно! Структура данных вычисляет текущий хеш-код, отличный от того, который использовался для хранения экземпляра, и отправляется на поиски в неправильном сегменте.
Вывод: лучше не использовать изменяемые поля для вычисления хеш-кода!
Производительность
Хэш-коды могут в конечном итоге вычисляться так часто, как вызывается hash Это может очень хорошо произойти в критически важных для кода частях кода, поэтому имеет смысл задуматься о производительности. И в отличие от equals
Если не используются сложные алгоритмы или задействовано много, много полей, арифметическая стоимость объединения их хеш-кодов настолько же незначительна, насколько и неизбежна. Но следует учитывать, все ли поля должны быть включены в вычисления! Особенно коллекции следует рассматривать с подозрением. Например, списки и наборы будут вычислять хеш для каждого из их элементов. Необходимость их вызова следует рассматривать в каждом конкретном случае.
Если производительность критична, использование equalsпеременных .
Но действует общее правило оптимизации: не делайте этого преждевременно! Используйте общий алгоритм хеширования, возможно, откажитесь от включения коллекций и оптимизируйте его только после того, как профилирование продемонстрировало потенциал для улучшения.
Столкновения
Если говорить о производительности, как насчет этой реализации?
Objects.hash
Это быстро, это точно. И равные объекты будут иметь одинаковый хеш-код, поэтому мы тоже хорошо справляемся с этим. В качестве бонуса, не изменяемые поля не участвуют!
Но помните, что мы говорили о ведрах? Таким образом, все экземпляры окажутся в одном и том же месте! Обычно это приводит к тому, что связанный список содержит все элементы, что очень плохо для производительности. Каждый @Override
public int hashCode() {
return 0;
}
Так что нам нужно как можно меньше предметов в одном ведре! Алгоритм, который возвращает сильно изменяющиеся хеш-коды, даже для очень похожих объектов, является хорошим началом.
Как туда добраться, частично зависит от выбранных полей. Чем больше деталей мы включаем в вычисления, тем больше вероятность того, что хеш-коды будут различаться. Обратите внимание, как это полностью противоречит нашим представлениям о производительности. Поэтому, что интересно, использование слишком большого или слишком небольшого количества полей может привести к снижению производительности.
Другой частью предотвращения столкновений является алгоритм, который используется для фактического вычисления хеша.
Вычисление хэша
Самый простой способ вычислить хеш-код поля — просто вызвать для него `hashCode`. Объединить их можно было бы вручную. Общий алгоритм состоит в том, чтобы начинать с некоторого произвольного числа и многократно умножать его на другое (часто небольшое простое число) перед добавлением хэша поля:
contains
Это может привести к переполнению, что не особенно проблематично, поскольку они не вызывают исключений в Java.
Обратите внимание, что даже отличные алгоритмы хеширования могут привести к нехарактерно частым коллизиям, если входные данные имеют определенные шаблоны. В качестве простого примера предположим, что мы вычислим хэш точек, добавив их координаты x и y. Может звучать не так уж плохо, пока мы не поймем, что часто имеем дело с точками на линии int prime = 31;
int result = 1;
result = prime * result + ((firstName == null) ? 0 : firstName.hashCode());
result = prime * result + ((lastName == null) ? 0 : lastName.hashCode());
return result;
f(x) = -x Столкновения, в изобилии!
Но опять же: используйте общий алгоритм и не беспокойтесь, пока профилирование не покажет, что что-то не так.
Резюме
Мы видели, что вычисление хеш-кодов — это что-то вроде сжатия равенства до целочисленного значения: у равных объектов должен быть один и тот же хеш-код, и из соображений производительности лучше всего, если как можно меньше одинаковых объектов используют один и тот же хеш.
Это означает, что x + y == 0hashCode
При реализации equals
- Используйте те же поля, которые используются в
hashCode - Лучше не включать изменяемые поля.
- Не
equalshashCode - Используйте общий алгоритм, если шаблоны во входных данных не противодействуют им.
Помните, что hashCode