Объяснение метода hashMap # hash (int)

Может кто-нибудь объяснить мне статический метод хэш-хэш (int) 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);
}

Пример облегчит переваривание.

Разъяснение Я знаю об операторах, таблицах истинности и побитовых операциях. Я просто не могу реально декодировать реализацию или комментарий. Или даже рассуждения позади.

Ответы

Ответ 1

>>> - это логический сдвиг вправо (без расширения знака) (JLS 15.19 Shift Operators), а ^ - побитовое exclusive-or (JLS 15.22.1 Побитовые операторы с целыми числами).

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

// HashMap.java -- edited for conciseness
static int indexFor(int h, int length) {
    return h & (length-1);
}

public V put(K key, V value) {
    int hash = hash(key.hashCode());
    int index = indexFor(hash, table.length);
    // ...
}

Итак, hash() пытается привести релевантность к более высоким битам, которые в противном случае будут скрыты (indexFor в основном отбрасывает более высокие бит h и принимает только нижние бит k, где length == (1 << k)).

Контрастируйте это с помощью способа Hashtable (который не должен иметь таблицу длины в две строки) использует хэш-код ключа.

// Hashtable.java -- edited for conciseness
public synchronized V get(Object key) {
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % table.length;
    // ...
}

Выполняя более дорогостоящую операцию % (вместо простой маскировки бит), производительность Hashtable менее чувствительна к хеш-кодам с плохим распределением в младших битах (особенно если table.length является простым числом).

Ответ 2

Я не знаю, как все смежные работы, но мотивация изложена в комментариях:

Способ реализации HashMap основан на том, что функция hashCode достаточно хорошо реализована. В частности, младшие бит хэш-значения должны распределяться равномерно. Если у вас много коллизий на младших битах, HashMap не будет работать хорошо.

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

Так что это делается, чтобы попытаться минимизировать конфликты (и, следовательно, повысить производительность) при наличии плохо реализованных методов hashCode.