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

Question

Хеш-функция

важна для реализации хеш-таблицы.Я знаю, что в Java объект имеет свой хэш-код, который может быть сгенерирован из слабой хэш-функции.

Ниже приведен один фрагмент, который является «дополнить хэш-функцию»

static int hash(Object x) {
    int h = x.hashCode();

    h += ~(h << 9);
    h ^=  (h >>> 14);
    h +=  (h << 4);
    h ^=  (h >>> 10);
    return h;
}

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

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

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

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

Answer 4

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

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

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

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

Answer 5

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

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

И это все.

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

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

Answer 6

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

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

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