Почему HashMap перефразирует хеш-код, предоставленный ключевым объектом?

Question

Я читаю код класса HashMap, предоставленного API Java 1.6, и не могу полностью понять необходимость следующей операции (находится в теле методов put и get):

int hash = hash(key.hashCode());

, где метод hash() имеет следующее тело:

 private static int hash(int h) {
         h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

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

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

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

Answer 1

Как писал Хелпер, он существует на всякий случай, если существующая хеш-функция для ключевых объектов неисправна и не выполняет достаточно хорошую работу по смешиванию младших битов.Согласно источнику , указанному в pgras,

 /**
  * Returns index for hash code h.
  */
 static int indexFor(int h, int length) {
     return h & (length-1);
 }

В хэш добавляется длина степени два (следовательно, length-1 гарантированно будет последовательностью1s).Из-за этого ANDing используются только младшие биты h.Остальная часть h игнорируется.Представьте себе, что по какой-либо причине исходный хеш возвращает только числа, кратные 2. Если бы вы использовали его напрямую, позиции с нечетным номером в хэш-карте никогда не использовались, что привело бы к увеличению числа коллизий в 2 раза.В действительно патологическом случае плохая хеш-функция может заставить хеш-карту вести себя больше как список, чем как контейнер O (1).

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

Answer 2

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

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

как n (числоэлементов в коллекции) / m (количество сегментов) становится больше, ваша производительность для чтения и записи становится все хуже и хуже.

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

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

Answer 3

Я где-то читал, что это сделано, чтобы обеспечить хорошее распределение, даже если ваша реализация hashCode, ну, эээ, отстой.

Answer 4

Как вы знаете, object.hashCode () может быть переопределен пользователями, так что действительно плохая реализация выкинет неслучайные биты более низкого уровня. Это может привести к переполнению некоторых ведер и оставлению многих ведер незаполненными.

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

Каждый бит преобразуется в другой бит следующим образом:

        h1 = h1 ^ h13 ^ h21 ^ h9 ^ h6     
        h2 = h2 ^ h14 ^ h22 ^ h10 ^ h7
        h3 = h3 ^ h15 ^ h23 ^ h11 ^ h8
        h4 = h4 ^ h16 ^ h24 ^ h12 ^ h9
        h5 = h5 ^ h17 ^ h25 ^ h13 ^ h10

. , , .

до 12:00.

Как видите, каждый бит h будет так далеко от самого себя. Так что это будет в значительной степени случайным и не собирается собирать какое-то конкретное ведро. Надеюсь, это поможет. Отправьте мне письмо, если вам нужен полный визуальный эффект.