В 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 : вопросов не вызывает.
Для того, чтобы понять зачем HashMap модифицирует хеш объекта, нужно заглянуть под капот этого HashMap. Указанный ассоциативный массив реализуется через бакеты. HashMap состоит из массива таких бакетов, к которым можно обращаться по индексу. Количество бакетов - это всегда результат возведения 2 в какую-то степень (2, 4, 8, 16 и т.д.). Каждый из бакетов представляет из себя коллекцию (список или дерево). Хорошее распределение по HashMap - это когда каждый из бакетов содержит примерно одинаковое количество записей (пар ключ-значение)
Теперь к сути. При записи нового объекта сначала ищется бакет, в который будет производиться запись. Для этого берется остаток от деления хеша на количество бакетов (своего рода хеш от хеша). Это и будет индекс бакета, в который попадёт новый элемент. Для наглядности, операцию остаток от деления на результат степени 2-х (а это количество бакетов) можно представить в виде поразрядного И хеша и (количество_бакетов - 1) , т.е.:
хэш % количество_бакетов = хэш & (количество_бакетов - 1)
Для примера покажу в двоичном варианте, где хэш равен 140, а количество бакетов 32 (результат должен быть равен 12):
10001100 % 0010000 = 10001100 & 00011111 = 00001100
Тут и выползает интересная особенность. На то, в какой бакет попадёт новая запись, влияют только младшие биты хеша. При реальных условиях количество бакетов обычно невысокое (к примеру 8192 вмещается в 14 битов) . А хеш имеет тип int, т.е. аж 32 бита!!!.
Поэтому и придумали различными манипуляциями подмешивать старшие биты хэша в младшие, чтобы улучшить распределение по бакетам и, как следствие, производительность.
Сборка персонального компьютера от Artline: умный выбор для современных пользователей