понимание хэш-кода

Хэш-функция - это любая четко определенная процедура или математическая функция, которая преобразует большой, возможно, переменного размера объем данных в небольшое число, обычно одно целое число, которое может служить индексом массива. Значения, возвращаемые хэш-функцией, называются хэш-значениями, хэш-кодами, хэш-суммами, контрольными суммами или просто хэшами. (wikipedia)

Используя более "человеческий" язык, хэш объекта - это короткое и компактное значение, основанное на свойствах объекта. То есть если у вас есть два объекта, которые каким-то образом различаются - вы можете ожидать, что их хэш-значения будут разными. Хороший алгоритм хэширования дает разные значения для разных объектов.

То, что вы обычно пытаетесь сделать с помощью хеш-алгоритма, - это преобразовать большой ключ поиска в маленькое неотрицательное число, чтобы вы могли найти связанную запись где-нибудь в таблице и сделать это еще быстрее, чем M log2 N (где M - стоимость «сравнения», а N - количество элементов в «таблице»), что типично для двоичного поиска (или поиска по дереву).

Если вам посчастливилось иметь идеальный хеш, вы знаете, что любой элемент вашего (известного!) Набора ключей будет хеширован с получением уникального, другого значения. Идеальные хэши в первую очередь интересны для таких вещей, как компиляторы, которым нужно искать ключевые слова языка.

В реальном мире у вас есть несовершенные хэши, когда несколько ключей имеют одно и то же значение. Это нормально: теперь вам нужно сравнить ключ только с небольшим набором соответствий-кандидатов (теми, которые хешируют это значение), а не с большим набором (полная таблица). Маленькие наборы традиционно называют «ведрами». Вы используете алгоритм хеширования для выбора сегмента, а затем используете другую структуру данных с возможностью поиска для самих сегментов. (Если известно или безопасно ожидается, что количество элементов в корзине действительно мало, линейный поиск не является необоснованным. Двоичные деревья поиска также разумны.)

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

В принципе, хэш-функция позволяет добиться того, что все биты в хэш-коде имеют примерно 50-процентную вероятность быть выключенными или включенными, учитывая конкретный хэшируемый элемент. Таким образом, не имеет значения, сколько "ведер" имеет ваша хэш-таблица (или, говоря иначе, сколько нижних битов вы берете для определения номера ведра) - если каждый бит настолько случаен, насколько это возможно, то элемент всегда будет отнесен к по сути случайному ведру.

Теперь, в реальной жизни, многие люди используют хэш-функции, которые не настолько хороши. В них есть некоторая случайность в некоторых битах, но не во всех. Например, представьте себе, что у вас есть хэш-функция, биты 6-7 которой смещены - скажем, в типичном хэш-коде объекта они имеют 75% шансов быть установленными. В этом выдуманном примере, если наша хэш-таблица имеет 256 ведер (т.е. номер ведра берется из битов 0-7 хэш-кода), то мы отбрасываем случайность, которая действительно существует в битах 8-31, и меньшая часть ведер будет иметь тенденцию к заполнению (т.е. те, чьи номера имеют установленные биты 6 и 7).

Дополнительная хэш-функция в основном пытается распределить случайность, имеющуюся в хэш-кодах, по большему числу битов. Поэтому в нашем гипотетическом примере идея заключается в том, что часть случайности из битов 8-31 будет смешана с младшими битами и разбавит смещение битов 6-7. Это все еще не будет идеальным, но будет лучше, чем раньше.

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

Например, если у вас есть хеш-таблица размером 10, вам не нужна хеш-функция, которая снова и снова возвращает хеш-значение 3. В противном случае этот конкретный сегмент приведет к тому, что время поиска будет O (n). Вам нужна хеш-функция, которая будет возвращать, например: 1, 9, 4, 6, 8 ... и гарантировать, что ни одна из ваших корзин не будет намного тяжелее других.

Для ваших проектов я бы порекомендовал вам использовать хорошо известный алгоритм хеширования, такой как MD5 или даже лучше, SHA, и использовать первые k битов, которые вам нужны, и отбросить остальные. Это проверенные временем функции, и вам, как программисту, будет разумно их использовать.

Этот код пытается улучшить качество хеш-значения путем перемешивания битов.

Общий эффект заключается в том, что для заданного x.hashCode () вы, надеюсь, получите лучшее распределение хеш-значений по всему диапазону целых чисел. Производительность некоторых алгоритмов улучшится, если вы начали с плохой реализации хэш-кода, но затем таким образом улучшили хэш-коды.

Например, hashCode () для скромного целого числа в Java просто возвращает целочисленное значение. Хотя это подходит для многих целей, в некоторых случаях вам нужен гораздо лучший хэш-код, поэтому использование hashCode через такую ​​функцию значительно улучшит его.

Это может быть что угодно, если вы придерживаетесь генерального контракта , описанного в документе, который, по моим собственным словам, таков:

• Если вы позвоните по номеру 100 (N) раз hashCode для объекта, все время должно возвращаться одно и то же значение, по крайней мере, во время выполнения этой программы (последующее выполнение программы может вернуть другое)
• Если o1.equals (o2) истинно, то o1.hashCode () == o2.hashCode () также должно быть истинным
• Если o1.equals (o2) ложно, то o1 .hashCode () == o2.hashCode () может быть правдой, но помогает, это не так.

Вот и все.

В зависимости от характера вашего класса hashCode () e может быть очень сложным или очень простым. Например, класс String , который может иметь миллионы экземпляров, нуждается в очень хорошей реализации hashCode и использует простые числа для уменьшения вероятности конфликтов.

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