Хеш-функция HashMap - Бинарный оператор

Question

Я просматривал исходный код HashMap, но бинарные операторы сильно сбивают с толку.

Я понимаю общее назначение ниже, справедливое распределение и приведу hashCode в пределы сегмента.

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

/**
     * Computes key.hashCode() and spreads (XORs) higher bits of hash
     * to lower.  Because the table uses power-of-two masking, sets of
     * hashes that vary only in bits above the current mask will
     * always collide. (Among known examples are sets of Float keys
     * holding consecutive whole numbers in small tables.)  So we
     * apply a transform that spreads the impact of higher bits
     * downward. There is a tradeoff between speed, utility, and
     * quality of bit-spreading. Because many common sets of hashes
     * are already reasonably distributed (so don't benefit from
     * spreading), and because we use trees to handle large sets of
     * collisions in bins, we just XOR some shifted bits in the
     * cheapest possible way to reduce systematic lossage, as well as
     * to incorporate impact of the highest bits that would otherwise
     * never be used in index calculations because of table bounds.
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

Было бы очень полезно, если бы кто-то мог помочь мне понять это.

Это не дубликат, потому что другие вопросы связаны с реализациями хеширования до Java 8.

Заранее спасибо

Answer 1

hashCode() возвращает int шириной 32 бита.

Внутренне HashMap сохраняет объекты в pow(2, n) корзинах или корзинах . Значение n может варьироваться - детали здесь не важны;важно то, что n обычно намного меньше 32 (количество битов в хэше).

Каждый объект помещается в одно из сегментов. Для достижения хорошей производительности желательно равномерно распределить объекты по ковшам. Вот где приходят хеши объектов: Самый простой способ выбрать сегмент - это взять самые младшие n биты хеш-кода объекта (используя простое побитовое И). Однако при этом используются только самые младшие биты n и игнорируется остальная часть хеша.

В комментариях авторы приводят аргумент, что это нежелательно. Они приводят примеры известных случаев использования, в которых хеши объектов будут систематически отличаться в битах, отличных от младших n. Это может привести к систематическим коллизиям, а систематические коллизии - плохие новости.

Чтобы частично решить эту проблему, они внедрили текущую эвристику, которая:

• сохраняет верхние 16 бит хеша
• заменяет младшие 16 битов на XOR старших 16 и нижних 16 бит.