Подтвердить что ты не робот

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

Я читаю код класса 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 использует хэш-таблицы с длиной в две строки, что       в противном случае возникают столкновения для хэш-кодов, которые не отличаются       в младших битах.

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

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

Ответ 2

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

Ответ 3

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

Предположим, вы продолжаете добавлять дополнительные элементы. Каждый раз, когда вы это делаете, и это не обновление, он запускает метод hashcode объекта и использует количество ведер с оператором modulo для определения того, в каком ведре должен идти объект.

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

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

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

Помните, что основное преимущество любой реализации хеширования - идеальная производительность O (1) для чтения и записи.

Ответ 4

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

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

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

        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

.,.

до h12.

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