Пользователь
0,0
рейтинг
17 февраля 2013 в 23:33

Разработка → Заметки о реализации 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.

Анализ алгоритма


Сначала сделаем несколько допущений:
1) Как уже сказано выше, будем работать с целыми числами.
2) Будем считать, что hashCode принимает значения от 0 до 232. То есть мы не будем работать с отрицательными значениями.
3) Будем считать, что переполнения при умножении и сложении не происходит. Будем использовать только небольшие исходные значения.
4) Будем считать, что данные, на основании которых строится hashCode распределены, равномерно.

Чтобы быть более конкретным, я стану рассматривать точки с целочисленными координатами (x, y) на плоскости в двухмерном пространстве, при условии, что x>= 0, y>=0.

Запишем hash функцию для точки P1 (x1, y1):
(p*q + x1)*q + y1 = h

h — значение hash функции.
Теперь я хочу рассмотреть какую-нибудь другую точку P2(x2, y2) у которой будет такая же hash функция. То есть это как раз случай коллизии:
(p*q + x2)*q + y2 = h

Вычтем из первого выражение второе:
q(x1-x2) + y1 — y2 = 0 (Обратите внимание, что множитель, содержащий p пропал после вычитания)

Вынесем q в правую часть:
(x1 — x2) / (y2-y1) = q (понятно, что знаменатель должен быть отличен от нуля)

Если подобрать такие значения x1, x2, y1, y2, что выполнится полученное равенство, то эти координаты будут соответствовать значениям аргумента hash функции, при которой возникнет коллизия.

Можно предложить такой вариант:
x1 = 38
x2 = 1
y2= 2
y1 = 1

То есть точки P(38, 1) и P(1, 2) имеют одинаковый hashCode… Я думал, что имея 4 миллиарда возможных значений для hash кода, можно было бы избежать коллизий хотя бы в квадрате 100x100!

Теперь рассмотрим случай n переменных, независимо изменяющихся от 0 до некоторого M. Хотелось бы найти максимальное значение M, такое, что хорошо написанная функция hashCode не имела бы коллизий на промежутке от 0 до M по всем n переменным. После недолгих раздумий, получаем значение для M:

Для случая точек на плоскости M принимает значение 65536.

Похоже, что формула, приведенная Блохом, будет давать приемлемое распределение hash кодов для случая 8 и более переменных.

Рассмотрим теперь точки в трехмерном пространстве. Напишем небольшую программу, которая в тройном цикле перебирает точки от 0 до 100 (всего миллион точек) и считает количество коллизий. Код этой программы элементарный, поэтому не буду его здесь приводить. Интересен результат: я получил 901692 коллизий! То есть чуть более, чем 90%. Получается, что Блох, под видом hash функции, предложил функцию для получения коллизий?

Хороший hashCode для случая двух переменных


Теперь попробуем построить хороший алгоритм для случая двух переменных (x1, y1). Чтобы равномерно раскидать значения x1 и y1 на числовой плоскости, воспользуемся умножением: умножим x1 на некоторое число p, а y1 — на q. Пока не будем накладывать на p и q никаких условий. Для получения значения hash функции, сложим эти произведения:
p*x1+q*y1=h

Воспользуемся приёмом, описанным выше: найдем x2, y2, такие, что значение hash функции выдаст коллизию.
p*x2+q*y2=h

Вычтем из первого равенства второе:
p*(x1-x2) + q(y1-y2) = 0
или
(x1-x2)/(y2-y1)=q/p (при условии, что знаменатель не равен нулю)


Если q взять равным 37, а p — 1, то получим формулу от Блоха.
Из последней формулы и из того факта, что мы работаем с целыми числами, следует:
1) Разность (x1-x2) пропорциональна q, разность (y2-y1) пропорциональна p.
2) Чем больше p и q, тем больше может быть расстояние между точками.
3) p и q должны быть взаимно простыми.
4) Имея верхнее ограничение на h=232, получаем, что каждое из произведений p*x1, q*y1 должны быть меньше, чем 232/2. Отсюда следует, что p и q должны быть меньше 32768. К примеру 32765 и 32767 Тут следует напомнить о нашем допущении: мы работаем только с положительными числами. Когда произойдет переполнение при сложении, мы окажемся в отрицательной части числовой оси. Предлагаю читателям поразмыслить над этим самостоятельно

Выводы


Как писал Дональд Кнут в главе про генератор псевдослучайных последовательностей, если алгоритм выглядит сложно и запутанно, это еще не означает, что он работает правильно (недословное изложение).

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

Если же вы бьетесь за производительность своего кода, учитываете все возможные мелочи, то вам, пожалуй, следует взглянуть на свои реализации hashCode() свежим взглядом. Учитывая, что хешируемые значения, могут быть не равномерно распределены для вашей конкретной бизнес области, вы сможете написать hash функцию с лучшим распределением hash кодов, чем любой сгенерированный вариант. Переписав hashCode(), вам, возможно, следует взглянуть на equals(): может быть вы сможете меньшим числом проверок вернуть значение false.

Спасибо тем, кто дочитал до конца.

Литература:
Bruce Eckel “Thinking in Java Third Edition”
Joshua Bloch “Effective Java: Programming Language Guide”
@esavin
карма
3,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (26)

  • –1
    А чем плох вариант «Поксорить хэшкоды всех полей»? По-моему там будет достаточно равномерное распределение.
    • +1
      В этом случае Вам будет тяжело по hash коду различить даже (1, 0) и (0, 1).
  • 0
    >odd prime
    Какое-то лишнее упоминание про «нечетность».
    Единственное четное простое число это 2…
    • 0
      Почему же лишнее, когда 2 не подходит?
  • 0
    Интересный эксперимент. Но диапазон от 0 до 100 не очень валидная выбора — очевидно, что (37*x + y) mod 2^31 будет тем дальше разносить соседние значения, чем больше сами значения. Поэтому на малых x,y плотность коллизий большая, и поэтому на малых значениях лУчший результат показывает выбор бОльшего простого множителя, который разносит соседние значения дальше. Есть подозрение, что если проверить диапазон (100 000, 100 100) — результат может заметно измениться.

    Но вообще — да, конечно, если нужно выжимать максимум, нужно внимательно смотреть на хэшфункции. Но тогда уж и на реализацию хэштаблицы нужно смотреть очень внимательно.
  • 0
    Руслан, я проверял этот диапазон. Результат тот же. Если в формуле (x1 — x2) / (y2-y1) = q умножить числитель и знаменатель на любое целое число, то коллизия останется, но ее можно будет сдвинуть по числовой оси.

    Прошу прощения, промахнулся с ответом.
    • 0
      Первый вопрос — а как вы думаете, почему в стандартной библиотеке используется chaining HashMap, когда open addressing, вообще говоря, в разы быстрее и в разы компактнее? Мое предположение — как раз потому, что chaining более толерантен к плохой хэш-функции. Тут уже правильно замечали — однократные коллизии мало что меняют, их практически нереально избежать для хэш-функции общего вида. Важно, чтобы не было явно выделенных точек, вокруг которых кучкуются значения хэша.

      Т.е. вопрос состоит в выборе критерии качества хэша. Вы берете просто количество коллизий — это ок для прикидки, но не вполне понятно, как это скажется на реальной работе. По-хорошему качество хэша надо проверять так: брать хэш-таблицу (конкретную реализацию), генерировать набор ключей, вставлять, смотреть на гистограмму коллизий (гистограмма в осях кратность коллизии/количество). Брать другую хэш-функцию, делать то же самое. Я так (буквально недавно) выбирал хэш-функцию для справочников. Это тоже не однозначный вариант, то он хоть ближе к ответу на вопрос «какая хэш-функция лучше на практике». Еще ближе был бы эксперимент с последующим чтением некой подвыборки ключей, и подсчетом среднего количества проб — тут прямая (хоть и не обязательно точная) оценка именно производительности — того, что, в конечном счете, и нужно от хорошего хэша.
      • 0
        Полностью согласен. Над конкретной задачей я бы работал примерно таким образом.
  • –2
    Еще я забыл написать в статье, что алгоритм от Блоха оставляет незадействованным промежуток от 0 до 17*372 (для двух переменных). Для 3-х переменных степень при 37 будет равна трем. А это 861101. Понятно, что после переполнения этот промежуток тоже будет использован, но как-то не очень красиво.

    Собственно, подобную ошибку допустил и я в своем примере. Правильная hash функция будет иметь вид:
    p*x1+q*y1-min(p,q)=h
  • +1
    Если не ошибаюсь, то про использование простого числа как основание хэша написал Дональд Кнут в третьем томе(про сортировку и поиск вроде как) и это не является какой-то магией.
  • 0
    Универсальная реализация, предложенная Блохом, на то и универсальная, чтобы не делать никаких предположений относительно значений ваших полей. В случае с int считается, что любое значение равновероятно. Было бы не очень красиво, если бы универсальная функция снижала число коллизий в диапазоне 0..100 или ещё каком-то. Может, у вас все числа в диапазоне от 2^30 до 2^30+100? Или идут с каким-нибудь хитрым шагом? Для любой хэш-функции можно подобрать неподходящие данные. И наоборот — если вы знаете о данных наперёд, ничто не мешает подобрать подходящую хэш-функцию. Например, в случае с тремя полями int, где каждое заведомо от 0 до 100, напишите (a*101+b)*101+c — у вас гарантированно не будет ни одной коллизии.
    • 0
      Универсальная реализация может быть хорошая, а может быть и не очень. Для примера из 3 short полей (как у Блоха) эта реализация не очень удачная. Если человеку нужно реализовать hashCode(), то он, обычно, или сгенерирует его с средствами IDE или обратиться к Блоху или Эккелю. И получит не очень хороший результат.

      Меня смущает, что Блох не проводит оценки качества своего алгоритма. И не заостряет внимание на то, что этим нужно заняться, если у вас высоконагруженная система.

      Кстати, для диапазона от 230 до 230+100 результат будет тот же.
  • +1
    Коллизии — это, конечно, интересно. Но более интересно, все-таки, распределение. Если одинаковый хэш будет у 3х элементов — это не страшно. Даже не смотря на то что все элементы будут иметь «близнецов». А вот если у 100, то это гораздо хуже.

    Дальше, Вы рассматриваете сплошной интервал, а это не отражает реальности. Если вам надо обращаться по значению в сплошном интервале или в почти заполненном, легче воспользоваться массивами или другими более продвинутыми структурами, которые дадут быстрый доступ к нужному элементу. В реальности интересен такой вопрос: какова будет вероятность получить L коллизий, если взять K случайных значений из N возможных?

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

    Ну и, естественно, бросаться переписывать хэш-функции стоит только тогда когда вы точно знаете, что причина низкой производительности в них.
    • 0
      Своей статьёй я хотел поднять вопрос, который особо нигде не обсуждается.

      Я встречал обсуждения про overhead на переключение между tread'ами, а про эффективность реализации hash функции — нет.

  • 0
    Множим первое значение на просто число. Множим второе значение на простое число. И так со всеми значениями. Результат ксорим. Даёт результат близкий к оптимальному.
    Простые числа вбираются так, чтобы они были максимально равномерно распределены в диапазоне 0..2^32. Т.е. для двух чисел оптимальными будут простые числа P1~2^8 P2~2^24.
    Быстро, хорошо, удобно, теоретически обосновано. Даёт отличное распределение.
    • 0
      И на всякий случай, вариант без умножения (таки довольно тяжёлая операция):
      /* Количество элементов равно количеству чисел, участвующий в генерации хеш-функции.
      Пространство хеш-функции делим пропорцинально кол-ву составляющий.
      В нашему случае - 32 бита хеш-функция делится на два диапазона по 16 бит.
      */
      const unsigned int P1= 70507 ;// Простое число для первого элемента.
      unsigned int counter1=P1; // Счётчик для первого элемента.
      unsigned int shift1=0; // Счётчик для сдвига второго числа.
      const unsigned int P2= 69221;// Простое число для второго элемента.
      unsigned int counter2=P2; // Счётчик для второго элемента.
      unsigned int shift2=15; // Счётчик для сдвига второго элемента.
      
      /* Возвращает хеш-функцию для любый двух чисел. */
      unsigned int getHash(unsigned int n1, unsigned int n2) {
        // Вычисляем первую составляющую (для первого числа).
        // Циклический сдвиг суммы счётчика и значения на указанное число бит).
        unsigned int v1=couter1+n1;
        v1=(v1<<shift1)|(v1>>31-shift1);
        counter1+=P1; // Увеличиваем счётчик для первого элемента.
        shift1=(shift1+1)&31; // Увеличиваем значение сдвига первого элемента.
        // Аналогично вычисляем второй элемент:
        unsigned int v2=couter2+n2;
        v2=(v2<<shift2)|(v2>>31-shift2);
        counter2+=P2; // Увеличиваем счётчик для второго элемента.
        shift2=(shift2+1)&31; // Увеличиваем значение сдвига второго элемента.
        // Вычисляем и возвращаем хэш:
        return v1 xor v2;
      }
      

      • 0
        Да, кстати, каюсь и посыпаю голову пеплом — это не хэш-функция в чистом виде. Это скорее многопоточный генератор псведослучайных чисел. Подсмотрен, если не ошибаюсь, в каких-то исходниках Java, где использовался в качестве генератора хэш-значения по-умолчанию для объектов (чистую хэш функцию от адреса использовать нельзя, так как из-за работы сборщика мусора, выравнивания и сжатия указателей высока вероятность того, что объекты будут выделяться по одним и тем же адресам и вызывать коллизии). В результате там есть такой алгоритм. Один из параметров — threadID. Второй — адрес объекта. Позволяет генерировать псевдослучайный хэш независимо для каждого потока. В нынешней Java-машине есть ключ, который этот режим включает (по-идее, повышает производительность если создаётся много объектов).
    • +1
      Не разделяю я любовь отечественных программистов к функции XOR.

      Берём P1=257, P2=16777259, рассматриваем две точки на плоскости.
      В промежутке от 0 до 1500 — нет коллизий. В промежутке от 0 до 3000 получаем уже 3504 коллизии. Заменяем XOR на обычное сложение — коллизий не будет и в более широком промежутке.
      • 0
        Есть мнение, что равномерность распределения тоже важна. Почему до 3000 рассматриваете? В общем случае, если у нас какие-то достаточно случайные значения на входе, то коллизий будет примерно одинаково, но xor даст более равномерное распределение хэшей. А если в дальнейшем хэш сужаеься до, например, восьми бит (и мало ли как это делается — например, xor'ом сех байт, как в некотопых библиотеках), то может иметь значение. Хотя, это все довольно спицифично для задачи.
        А любовь растет, на сколько я понимаю, из мнения, что две различные операции уменьшают вероятность коллизий при дальнейшей обработке. Ведь мы не знаем, кто и как будет использовать результат — будет ли там сложение/вычитание или xor и с чем.
        • +1
          Интервал до 3000 я взял просто для примера (чтобы не долго считалось). Если Ваш алгоритм вычисление хеша имеет коллизии на таком интервале, то он будет иметь их и на большем интервале. А для моего алгоритма есть теоретическое обоснование отсутствия коллизий на интервале от 0 до 216. Я не предлагаю сейчас начинать спор о допустимости использования функции XOR. Для двух переменных это не очень оправдано, а, возможно, для 10 — будет в самый раз.
  • 0
    Только вот для HaspMap не так уж требуются хэши в диапазоне 0...232, он всё равно их урежет до размера внутренней таблицы.
    • –1
      Одно дело иметь хорошую hash функцию и осознанно не использовать всех ее свойств, и совсем другое дело думать, что имеешь хорошую hash функцию, но ошибаться.
      • +1
        С точки зрение чего она хорошая? Вы посмотрите в исходники HashMap — там полученное от объекта значение хэш-код ещё раз трансформируется (метод hash()), так что там, где у вас коллизий не было, в таблице они могут быть.
        • –1
          Вы совершенно правы. Только нужно понимать, что если у Вас в исходной hash функции не было коллизий, то HashMap может странсформирует Ваш hashCode в коллизию для другого hash кода, а может и нет. А если у Вас изначально есть коллизия, то и в результате коллизия будет гарантирована.
  • +2
    Для тех, кто все еще не верит, что hash функция от Блоха не очень хороша, проведем небольшой эксперимент.
    Возьмем промежуток от 0 до 216, возьмем случайную точку на плоскости примерно из середины этого промежутка. Координаты точки: (32127, 32123). Переберем все точки на заданном промежутке и посчитаем коллизии.
    У меня получилось 2114. Много это или мало — пусть каждый решает сам.
  • 0
    bugs.sun.com/bugdatabase/view_bug.do?bug_id=4045622


    Of the remaining four, I'd probably select P(31), as it's the cheapest to calculate on a
    RISC machine (because 31 is the difference of two powers of two). P(33) is
    similarly cheap to calculate, but it's performance is marginally worse, and
    33 is composite, which makes me a bit nervous.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.