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

Question

Может кто-нибудь объяснить мне статический метод HashMap # hash (int)?

Каково основание для создания равномерно распределенных хэшей?

/**
 * 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);
}

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

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

Answer 1

>>> - логическое смещение вправо (без расширения знака) ( JLS 15.19 Операторы сдвига ), а ^ - побитовое исключающее или ( JLS 15.22.1 Integer Bitwise Операторы ).

Относительно того, почему это делается, в документации есть подсказка: 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 - простое число) .

Answer 2

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

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

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

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