Объяснение констант, используемых при вычислении значения хэш-кода java.util.hash

Может кто-нибудь объяснить значение этих констант и почему они выбраны?

static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

источник: библиотека java-se6

Ответы

Ответ 1

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

Java-хэш-таблицы работают следующим образом:

  • Они запрашивают ключевой объект для создания своего хэш-кода. Реализация метода hashCode(), скорее всего, будет отличаться переменным качеством (в худшем случае, возвращая постоянное значение!) И определенно не будет адаптирована к конкретной хеш-таблице, с которой вы работаете.
  • Затем они используют указанную выше функцию для смешивания бит бит, так что информация, содержащаяся в высоких битах, также перемещается вниз к младшим битам. Это важно, потому что следующий...
  • Они берут мод хеш-кода (w.r.t. количество записей массива хеш-таблицы), чтобы получить индекс в массив цепей хеш-таблицы. Существует явная вероятность того, что массив хэш-таблицы будет иметь размер, эквивалентный мощности 2, поэтому смешение бит на шаге 2 важно, чтобы гарантировать, что они не просто отброшены.
  • Затем они пересекают цепочку, пока не дойдут до записи с помощью равного ключа (в соответствии с методом equals()).

Чтобы завершить изображение, количество записей в массиве хэш-таблицы является непостоянным; если цепи становятся слишком длинными, массив заменяется новым более крупным массивом, и все становится перефразированным. Это относительно быстро и имеет хорошие показатели производительности для обычных шаблонов использования (например, много put(), за которыми следуют серии get() s).

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

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

Ответ 2

Я также задавался вопросом о таких "волшебных" числах. Насколько я знаю, это магические числа.
Было доказано обширное тестирование того, что нечетные и простые числа имеют интересные приоритеты, которые можно использовать в хэшировании (избегайте первичной/вторичной кластеризации и т.д.). Я считаю, что большая часть чисел приходит после исследований и тестирования, которые статистически подтверждают хорошие распределения. Почему именно эти цифры делают это, я понятия не имею, но у меня такое впечатление (надеюсь, коллеги могут меня исправить, если я уйду) ни исполнители не знают, почему эти конкретные числа представляют эти качества.