Понимание странной хэш-функции Java

Ниже приведен исходный код для хэш-функции в java.util.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

Dunno 'об английском языке, но вот какой-то код и образец вывода:

public static void main ( String[] args ) {
    int h = 0xffffffff;
    int h1 = h >>> 20;
    int h2 = h >>> 12;
    int h3 = h1 ^ h2;
    int h4 = h ^ h3;
    int h5 = h4 >>> 7;
    int h6 = h4 >>> 4;
    int h7 = h5 ^ h6;
    int h8 = h4 ^ h7;

    printBin ( h );
    printBin ( h1 );
    printBin ( h2 );
    printBin ( h3 );
    printBin ( h4 );
    printBin ( h5 );
    printBin ( h6 );
    printBin ( h7 );
    printBin ( h8 );

}

static void printBin ( int h ) {
    System.out.println ( String.format ( "%32s", 
        Integer.toBinaryString ( h ) ).replace ( ' ', '0' ) );
}

Какие принты:

11111111111111111111111111111111
00000000000000000000111111111111
00000000000011111111111111111111
00000000000011111111000000000000
11111111111100000000111111111111
00000001111111111110000000011111
00001111111111110000000011111111
00001110000000001110000011100000
11110001111100001110111100011111

Итак, код разбивает хеш-функцию на шаги, чтобы вы могли видеть, что происходит. Первый сдвиг 20 позиций xor со вторым сдвигом 12 позиций создает маску, которая может перевернуть 0 или более из нижних 20 бит int. Таким образом, вы можете получить некоторую случайность, вставленную в нижние биты, которая использует потенциально более распределенные более высокие бит. Затем он применяется через xor к исходному значению, чтобы добавить эту случайность к младшим битам. Второй сдвиг в 7 позициях x или сдвиг 4 позиций создает маску, которая может перевернуть 0 или более нижних 28 бит, что снова приводит к некоторой случайности к младшим битам и к некоторым из более значительных, используя капитализацию предыдущего xor которые уже рассматривали некоторые из распределений в младших битах. Конечным результатом является более плавное распределение бит через хэш-значение.

Так как hashmap в java вычисляет индекс bucket, комбинируя хэш с количеством ведер, вам нужно иметь равномерное распределение младших бит хеш-значения, чтобы равномерно распределять записи в каждом ковше.

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

Ответ 2

>>> - бит-сфера с нулевым заполнением.

^ является XOR.

XOR также называется исключительным или - это математический оператор, который объединяет два числа. См. http://en.wikipedia.org/wiki/Exclusive_or

Правильный бит-бит на n похож на сброс n младших бит от числа. Поэтому, если число 00010111, и вы сдвинули его на 1, вы получите 00001011.

Ответ 3

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

операции должны использовать цепочку вычислений для достижения лавины. Лавина означает, что один бит разницы во входе будет около 1/2 выходных бит будут отличаться.

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