Понимание странной хэш-функции 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);
}
Источник

6 ответов

Решение

Не знаю насчет английского, но вот код и пример вывода:

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 битов целого числа. Таким образом, вы можете вставить некоторую случайность в нижние биты, которые используют потенциально лучше распределенные старшие биты. Затем это применяется через xor к исходному значению, чтобы добавить эту случайность к младшим битам. Второе смещение на 7 позиций или смещение на 4 позиции создает маску, которая может переворачивать 0 или более из нижних 28 битов, что снова вносит некоторую случайность в младшие биты и в некоторые из наиболее значимых из них, используя заглавную букву предыдущего хора. который уже адресовал часть распределения в младших битах. Конечным результатом является более плавное распределение битов по значению хеша.

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

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

Источник

>>> битовое смещение с нулевой заливкой.

^ это XOR.

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

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

Источник

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

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

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

Источник

^ поразрядно XOR, >>> бит сдвигается.

Источник

>>> представляется беззнаковым правым побитовым сдвигом, и ^ поразрядно XOR

http://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html

Источник

Это комбинация побитового исключающего ИЛИ и беззнакового правого сдвига.

Смотрите здесь для более подробного объяснения: http://www.roseindia.net/java/master-java/bitwise-bitshift-operators.shtml

Источник
Другие вопросы по тегам