Разработка метода hashCode Java
Я изучаю пункт 9, Эффективная Java [Всегда переопределять hashcode(), когда вы переопределяете equals].
У меня есть несколько вопросов относительно замечаний автора:
- Автор говорит:
На этапе 1 используется ненулевое начальное значение, поэтому на значение хеш-функции будут влиять начальные поля, чье значение хеш-функции, вычисленное на этапе 2.а, равно нулю. Если бы нулевое значение использовалось в качестве начального значения на шаге 1, то на общее значение хеша не влияли бы любые такие начальные поля, которые могли бы увеличить коллизии. Значение 17 произвольно.
Шаг 2.a:
Для каждого значимого поля f в вашем объекте (то есть каждого поля, которое учитывается методом equals), выполните следующие действия: a. Вычислить int хеш-код c для поля:
я. Если поле логическое, вычислите (f? 1: 0) .
II. Если поле является байтом, символом, коротким или int, вычислите (int) f.
III. Если поле длинное, вычислите (int) (f^ (f >>> 32)) .
внутривенно Если поле является плавающим, вычислить Float.floatToIntBits (f).
v. Если поле двойное, вычислите Double.doubleToLongBits(f), а затем хешируйте полученное значение long, как в шаге 2.a.iii.
VI. Если поле является ссылкой на объект, и метод equals этого класса сравнивает поле путем рекурсивного вызова equals, рекурсивно вызывайте hashCode для поля. Если требуется более сложное сравнение, вычислите "каноническое представление" для этого поля и вызовите hashCode для канонического представления. Если значение поля равно нулю, вернуть 0 (или некоторую другую константу, но 0 - традиционная).
VII. Если поле является массивом, обрабатывайте его так, как если бы каждый элемент был отдельным полем. То есть вычислите хеш-код для каждого значимого элемента, применив эти правила рекурсивно, и объедините эти значения для шага 2.b. Если каждый элемент в поле массива является значимым, вы можете использовать один из методов Arrays.hashCode, добавленных в выпуске 1.5.
Предположим, результат рассчитывается как:
result = 31 * result + areaCode;
result = 31 * result + prefix;
result = 31 * result + lineNumber;
В случае, если начальное значение результата равно 0, а все приведенные выше поля равны 0, результат останется равным 0. Но даже если результат изначально не равен 0, результат будет составлять одну и ту же константу каждый раз, когда начальные поля равны 0, что будет: 31*(31*(31*17)). Как это значение поможет уменьшить коллизии?
- Последний абзац гласит:
Многие классы в библиотеках платформы Java, такие как String, Integer и Date, включают в свои спецификации точное значение, возвращаемое их методом hashCode как функцию значения экземпляра. Как правило, это не очень хорошая идея, поскольку она серьезно ограничивает вашу способность улучшать хэш-функцию в будущих версиях. Если вы оставите детали хэш-функции неуказанными и обнаружите недостаток или обнаружите более качественную хеш-функцию, вы можете изменить хеш-функцию в следующем выпуске, будучи уверенными, что клиенты не зависят от точных значений, возвращаемых хеш-функцией.
Что он имеет в виду, говоря, что точное значение, возвращаемое hashCode, является функцией значения экземпляра?
Заранее благодарю за любую помощь.
5 ответов
Как это значение поможет уменьшить коллизии?
Хеш-коллизия достигается в основном хорошим распределением по всему хеш-диапазону (здесь целочисленный тип).
Определив 0 в качестве начального значения для вычисления результата хеширования, вы получите несколько ограниченное распределение в небольшом диапазоне. Объекты, которые незначительно отличаются - возможно, только в некоторых полях - создают хеш-коды, которые находятся недалеко друг от друга. Это делает коллизии хешей более вероятными.
Определяя ненулевое начальное значение, вы просто увеличиваете промежутки между вычисленными хеш-кодами для объектов, которые отличаются лишь незначительным образом. Таким образом, вы лучше используете диапазон хеширования и эффективно делаете коллизии хешей менее вероятными.
Что он имеет в виду, говоря, что точное значение, возвращаемое hashCode, является функцией значения экземпляра?
Это просто означает, что вы должны вычислить хеш-код, используя значение объекта, то есть значения его полей. Вы уже сделали это в своем примере, и я думаю, что вы уже безоговорочно поняли это.
Но: Джошуа Блох намеревался сказать что-то еще с этим абзацем: он хотел предупредить вас о том, что вы не документируете точную функцию вычисления хеш-кода. Если вы сделаете это, вы ограничитесь тем, что больше не сможете изменять реализацию в будущих выпусках, потому что некоторые пользователи могут ожидать конкретной реализации, и вы нарушите некоторый код в зависимости от вашего.
Смотрите этот пример:
String a = "Abc";
String b = "Abc";
String c = "Pqr";
System.out.println(" "+a.hashCode()+" "+b.hashCode()+" "+c.hashCode());
Выход: 65602 65602 80497
Что ясно показывает, что hashCode() строки зависит от значений.
Извлечение из документации hashCode():
int java.lang.String.hashCode()
Возвращает хеш-код для этой строки. Хеш-код для объекта String вычисляется как
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
используя int арифметику, где s[i] - это i-й символ строки, n - длина строки, а ^ - возведение в степень. (Значение хеша пустой строки равно нулю.)
Прежде всего я хочу сказать очень важную вещь, которая часто не четко сформулирована:
Реализация хеш-кода для большинства случаев не имеет значения. Это сводится только к проблеме производительности. Так что если у вас есть проблемы с хеш-кодом и идентификацией объекта, просто верните -1. У вас будет плохая производительность, но надежная и правильная реализация. Но до тех пор, пока у вас не появятся тысячи объектов, использующих хеш-код, вы не сможете распознать низкую производительность. Кстати: "Столкновение" выглядит как значимое слово в контексте хэш-кода. Да, но только если производительность действительно является проблемой. "Столкновение" значений хеш-кода не означает, что ваша программа работает неправильно. Это означает, что ваша программа может работать медленнее. Поскольку доступ с ключом к карте вызовет последовательную итерацию по объектам с одинаковым хеш-кодом. В высокопроизводительных средах это может быть проблемой. В большинстве случаев нет.
Но что ВАЖНО, если вы переопределяете хеш-код: вы должны реализовать его ПРАВИЛЬНО. Поэтому определение всегда должно выполняться: если equals возвращает true, хеш-код должен возвращать одно и то же значение.
Еще одна вещь: хотя вы случайно не сталкиваетесь с проблемами, вычисление хэш-кода для неизменяемых значений является плохой идеей. Это связано с тем, что после использования хеш-кода объект помещается в специальную позицию на "карте". Если значения изменяют хеш-код, зависит от того, может ли этот объект быть потерян или он станет труднодоступным. Это повлияет на правильность вашей программы.
Вывод: используйте хеш-код, только если вам действительно нужна производительность. И тогда вы должны убедиться, что вы применяете это правильно. Здесь легко делать ошибки, но эти ошибки могут быть труднее всего идентифицировать.
Реализация hashCode в Effective Java специально указывает вам выбрать ненулевое значение для начального значения результата. Что касается вашего второго вопроса, предполагается, что hashCode выдаст то же значение, когда внутреннее состояние, используемое для сравнений объекта сравнения, одинаково. Таким образом, тот факт, что вы получите одно и то же значение, когда все переменные экземпляра равны нулю, соответствует контракту hashCode. Обратите внимание, что весь подзаголовок: "Всегда переопределять hashCode, когда вы переопределяете equals".
По первому вопросу: если два объекта равны, они должны возвращать одно и то же хеш-значение, это причина, по которой переопределение хеш-метода является хорошей идеей, когда вы переопределяете метод equals. Он не предотвращает столкновения равных объектов, но снижает вероятность возникновения столкновений, когда объекты не равны, что более важно, поскольку мы хотим иметь возможность находить уникальные объекты как можно быстрее.
Что касается вашего второго вопроса, я не претендую на большой опыт разработки Hash-кода, однако я считаю, что он имеет в виду, что некоторые объекты могут возвращать только одно значение Hash (например, Singleton).
Он говорит, что помещать это значение в документацию - это плохая практика, так как вы можете захотеть изменить хэш-функцию позже, или другие переменные в хэш-функции могут измениться позже, изменяя возвращаемое значение.
В любом случае указание возвращаемого значения или использование указанного возвращаемого значения - плохая идея.