Почему HashMap перехеширует хэш-код, предоставленный ключевым объектом?
Я читаю код класса HashMap, обеспеченного Java 1.6 API и не могущего полностью понять потребность следующей операции (найденный в теле помещенных и получить методы):
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 использует power-two хеш-таблицы длины, это иначе встречается с коллизиями для хэш-кодов, которые не отличаются по более низким битам.
Я действительно понимаю, что Иранское агентство печати значения ключа хранится в массиве структур данных, и что индексное местоположение объекта в этом массиве определяется его хешем. То, что мне не удается понять, - то, как был бы эта функция добавлять любое значение к распределению хеша.
2 ответа
Как писал Помощник, он существует на тот случай, если существующая хеш-функция для ключевых объектов неисправна и не выполняет достаточно хорошую работу по смешиванию младшие биты. Согласно источнику , цитируемому pgras,
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
хеш-код соединяется с длиной, равной степени двойки (следовательно, длина-1 гарантированно является последовательностью 1с). Из-за этого операции AND используются только младшие биты h . Остальная часть h игнорируется. Представьте себе, что по какой-то причине исходный хэш возвращает только числа, делящиеся на 2. Если бы вы использовали его напрямую, нечетные позиции хеш-карты никогда не использовались бы, что привело бы к увеличению числа коллизий в 2 раза. В действительно патологическом случае плохая хеш-функция может заставить хэш-карту вести себя больше как список, чем как контейнер O (1).
Инженеры Sun должны были провести тесты, которые показали, что слишком много хэш-функций недостаточно случайны в своих младших битах и что многие хэш-карты недостаточно велики, чтобы когда-либо использовать старшие биты. В этих обстоятельствах битовые операции в хэше HashMap (int h) могут обеспечить чистое улучшение по сравнению с большинством ожидаемых вариантов использования (из-за более низкой частоты конфликтов), даже если требуются дополнительные вычисления.
Я где-то читал, что это делается для обеспечения хорошего распределения, даже если ваша реализация hashCode, ну, эээ, отстой.