Смысл функции hash() в HashMap (java 7 и java 8)

233
21 августа 2018, 01:50

В Java 7 функция hash() класса HashMap имеет следующий вид:

/**
  * Applies a supplemental hash function to a given hashCode, which
  * defends against poor quality hash functions.  This is critical
  * because HashMap uses power-of-two length hash tables, that
  * otherwise encounter collisions for hashCodes that do not differ
  * in lower bits. Note: Null keys always map to hash 0, thus index 0.
  */
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);
}

Из всего этого я понимаю только первый комментарий (перед функцией). Данная функция используется "на всякий случай" - в случае, если hashCode объекта будет плохой ("низкого качества"), то данная функция должна обеспечить лучший разброс значений. Это важно, потому что HashMap использует хэш-таблицы, размер которых - степень двойки (16, 32, 64 и т.д.), и в противном случае, при использовании хэш-кодов, у которых в младших битах есть совпадения (при использовании хэш-функций "низкого качества") возникают коллизии.

А что значит комментарий внутри функции?

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);

Почему побитовые сдвиги и XOR - понятно, потому что данные операции выполняются быстрее, чем операции сложения и умножения. Но почему именно эти цифры (20, 12, 7, 4)? И каким образом эти преобразования делают более разнообразными младшие биты хэш-кодов?

И почему в Java 8 эта функция изменилась следующим образом?

static final int hash(Object key) {
   int h;
   return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

В чём её смысл? Часть (key == null) ? 0 : вопросов не вызывает.

Answer 1

Для того, чтобы понять зачем HashMap модифицирует хеш объекта, нужно заглянуть под капот этого HashMap. Указанный ассоциативный массив реализуется через бакеты. HashMap состоит из массива таких бакетов, к которым можно обращаться по индексу. Количество бакетов - это всегда результат возведения 2 в какую-то степень (2, 4, 8, 16 и т.д.). Каждый из бакетов представляет из себя коллекцию (список или дерево). Хорошее распределение по HashMap - это когда каждый из бакетов содержит примерно одинаковое количество записей (пар ключ-значение)

Теперь к сути. При записи нового объекта сначала ищется бакет, в который будет производиться запись. Для этого берется остаток от деления хеша на количество бакетов (своего рода хеш от хеша). Это и будет индекс бакета, в который попадёт новый элемент. Для наглядности, операцию остаток от деления на результат степени 2-х (а это количество бакетов) можно представить в виде поразрядного И хеша и (количество_бакетов - 1) , т.е.:

хэш % количество_бакетов = хэш & (количество_бакетов - 1)

Для примера покажу в двоичном варианте, где хэш равен 140, а количество бакетов 32 (результат должен быть равен 12):

10001100 % 0010000 = 10001100 & 00011111 = 00001100 

Тут и выползает интересная особенность. На то, в какой бакет попадёт новая запись, влияют только младшие биты хеша. При реальных условиях количество бакетов обычно невысокое (к примеру 8192 вмещается в 14 битов) . А хеш имеет тип int, т.е. аж 32 бита!!!.

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

READ ALSO
Конкурентное чтение из списка

Конкурентное чтение из списка

Является ли кеш со следующей реализацией потокобезопасным для чтения? Кешируемые данные хранятся в статическом списке listРеализация заполнения...

255
Поиск по слову java

Поиск по слову java

Скажите пожалуйста, в чем ошибкаДелаю поиск по слову

341
Запуск отдельного теста в тест-классе используя JUnit Parameterized

Запуск отдельного теста в тест-классе используя JUnit Parameterized

Не могу запустить отдельный тест в параметризированном тестовом классеЕсли запускать весь класс - всё работает, а вот отдельно - нет

284
Что такое legacy code?

Что такое legacy code?

Не могу найти переводМожете объяснить в двух словах что это такое? Что за понятие?

278