Часто на собеседованиях приходится спрашивать о функции hashCode().
Я не буду здесь перечислять все свойства этой функции и ее связь с другой, не менее важной функцией равенства().
Эта информация есть во всех учебниках по Java и повторять ее здесь я не вижу смысла.
Я хотел бы остановиться только на одном свойстве: hashCode должен быть равномерно распределен по диапазону функции.
Я подумал: «Что гарантирует равномерное распределениеЭ» Забегая вперед, скажу, что пришел к довольно интересным выводам.
Хотелось бы, чтобы меня поправили, если я где-то допустил ошибку в своих рассуждениях.
Давайте спросим Гуру
Сначала я решил просмотреть документацию Java по Object.hashCode().Как все видят, никакой интересующей нас информации там нет. После этого я пошел к Гуру.
Брюс Оккель написал 5 страниц, кивнул Блоху (вернее, скопировал у него), привел пример со строками и в конце посоветовал использовать «полезные библиотеки».
Джошуа Блох справился лучше: он предложил алгоритм вычислений, рассказал о пользе простых чисел и… еще привел пример.
Не могу не процитировать:
Множитель 37 был выбран потому, что это нечетное простое число.Никто из авторов не удосужился проанализировать данный алгоритм и доказать его корректность.… Преимущества использования простых чисел менее очевидны, но для этой цели традиционно используются простые числа.
Алгоритм (вольно перефразированный)
1) Возьмем число, отличное от нуля, например 17. Для удобства назовем его п.Присвойте переменную результата этому начальному значению (результат = p).
2) Для каждого поля вычисляем hashCode c по некоторым правилам.
Эти правила нас сейчас не особо интересуют, на результат они не влияют. Для простоты мы будем работать с целыми числами (int) и возьмем hashCode равным значению самого числа.
3) Объединить результат и полученный хэш-код с помощью: result = result * q + c, где q = 37, потому что, как мы помним, он нечетный и простой.
4) Вернуть результат.
Алгоритмический анализ
Сначала сделаем несколько предположений: 1) Как уже говорилось выше, мы будем работать с целыми числами.2) Будем считать, что hashCode принимает значения от 0 до 2. 32 .
То есть мы не будем работать с отрицательными значениями.
3) Будем считать, что при умножении и сложении переполнения нет. Мы будем использовать только небольшие начальные значения.
4) Будем считать, что данные, на основе которых строится хеш-код, распределены равномерно.
Точнее, я буду рассматривать точки с целочисленными координатами (x, y) на плоскости в двух измерениях при условии, что x> = 0, y> =0. Напишем хеш-функцию для точки P1(x1,y1):
(p*q + x1)*q + y1 = hh — хеш-значение функции.
Теперь я хочу рассмотреть другую точку P2(x2, y2), которая будет иметь такую же хеш-функцию.
То есть это всего лишь случай коллизии:
(p*q + x2)*q + y2 = hВычтем второе выражение из первого:
q(x1-x2) + y1 - y2 = 0 (обратите внимание, что множитель, содержащий p, после вычитания отсутствует)Переместим q в правую часть:
(x1 - x2)/(y2-y1) = q (очевидно, что знаменатель должен быть ненулевым)Если выбрать значения x1, x2, y1, y2 такие, чтобы выполнялось полученное равенство, то эти координаты будут соответствовать значениям хеш-аргумента функции, при которой происходит коллизия.
Вы можете предложить такой вариант:
х1 = 38 х2 = 1 у2= 2 у1 = 1То есть точки P(38, 1) и P(1, 2) имеют один и тот же hashCode. Я думал, что при 4 миллиардах возможных значений хэш-кода можно будет избежать коллизий хотя бы в квадрат 100х100! Теперь рассмотрим случай, когда n переменных независимо изменяются от 0 до некоторого M. Я хотел бы найти максимальное значение M такое, чтобы хорошо написанная функция hashCode не имела коллизий в интервале от 0 до M для всех n переменных.
После некоторых размышлений мы получаем значение M: 
Для случая точек на плоскости M принимает значение 65536.
Кажется, что формула Блоха даст приемлемое распределение хеш-кодов для случая 8 и более переменных.
Давайте теперь рассмотрим точки в трехмерном пространстве.
Давайте напишем небольшую программу, которая в тройном цикле перебирает точки от 0 до 100 (всего миллион точек) и подсчитывает количество коллизий.
Код этой программы элементарный, поэтому приводить его здесь не буду.
Результат интересный: я получил 901692 столкновения! Это чуть больше 90%.
Получается, Блох под видом хеш-функции предложил функцию получения коллизий?
Хороший хэш-код для случая двух переменных
Теперь попробуем построить хороший алгоритм для случая двух переменных (x1, y1).Чтобы равномерно распределить значения x1 и y1 на числовой плоскости, воспользуемся умножением: умножим x1 на некоторое число p, а y1 на q. На данный момент мы не будем налагать никаких условий на p и q. Чтобы получить хеш-значение функции, добавьте эти продукты:
p*x1+q*y1=чДавайте воспользуемся описанной выше техникой: найдем x2, y2 такие, что хэш-значение функции вызовет коллизию.
p*x2+q*y2=чВычтем второе из первого равенства:
р*(х1-х2) + q(y1-y2) = 0 или (x1-x2)/(y2-y1)=q/p (при условии, что знаменатель не равен нулю)Если q принять равным 37 и p = 1, то получим формулу Блоха.
Из последней формулы и того, что мы работаем с целыми числами, следует: 1) Разность (х1-х2) пропорциональна q, разность (y2-y1) пропорциональна p. 2) Чем больше p и q, тем больше может быть расстояние между точками.
3) p и q должны быть взаимно простыми.
4) Наличие верхнего предела h=2 32 , мы находим, что каждое из произведений p*x1, q*y1 должно быть меньше 2 32 /2. Отсюда следует, что p и q должны быть меньше 32768. Например, 32765 и 32767. Здесь следует вспомнить наше предположение: мы работаем только с положительными числами.
Когда произойдет переполнение при сложении, мы окажемся на отрицательной стороне числовой прямой.
Предлагаю читателям подумать об этом самостоятельно.
выводы
Как писал Дональд Кнут в главе о генераторе псевдослучайных последовательностей, тот факт, что алгоритм выглядит сложным и запутанным, не означает, что он работает правильно (не дословно).Те, кто использует реализацию хеш-функции от Джошуа Блоха, но имеет большое количество хешируемых переменных, могут быть спокойны.
Кроме того, тем, для кого различные типы хэш-коллекций не являются узким местом в производительности, не стоит беспокоиться.
Если у вас проблемы с производительностью вашего кода, принимая во внимание все возможные мелочи, то вам, вероятно, стоит по-новому взглянуть на ваши реализации hashCode().
Учитывая, что хэш-значения могут быть неравномерно распределены для вашей конкретной бизнес-домены, вы сможете написать хэш-функцию с лучшим распределением хеш-кодов, чем любой сгенерированный вариант. Переписав hashCode(), вы, возможно, захотите взглянуть на методquals(): возможно, вы сможете вернуть false с меньшим количеством проверок.
Спасибо тем, кто дочитал до конца.
Литература: Брюс Экель «Мышление на Java, третье издание» Джошуа Блох «Эффективная Java: руководство по языку программирования» Теги: #java #hashcode #Высокая производительность #java #Алгоритмы
-
Обновление Для Ide Embitz 1.11
19 Oct, 24 -
Простые Заметки О Веб-Разработке
19 Oct, 24
