Каков трюк метода hash() в реализации Java HashMap?

Возможный дубликат:
Понимание странной хэш-функции Java

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

Я не совсем понимаю принцип алгоритма этой реализации. Любое объяснение или любое другое сообщение, на которое я могу ссылаться? Спасибо!

UPDATE

Спасибо всем за ответы и комментарии. На самом деле я понимаю, как работает хеш, но не знаю, почему этот код обеспечит a bounded number of collisions, как говорится в комментарии. Есть ли теоретическая проверка?

Ответы

Ответ 1

Основная цель - генерировать очень разные значения для аналогичных входных параметров и минимизировать количество столкновений. http://en.wikipedia.org/wiki/Hash_function

Эта реализация является лишь одним из удовлетворительных вариантов многих возможных функций.

Ответ 2

Эта функция помогает лучше избегать столкновений в HashMap.

Если у вас хорошая реализация hashCode, вы все равно можете получить столкновение только потому, что вы берете hashCode % size для обнаружения ведра для объекта.

Пример:

Предположим, что размер вашего HashMap равен 20.

  • Вы рассчитали hashCode() для object1 и получите 401. Ведро 401 % 20 = 1.
  • Вы рассчитали hashCode() для object2 и получите 3601. Ведро 3601 % 20 = 1
  • Вы рассчитали hashCode() для object3 и получите 1601. Ведро 1601 % 20 = 1.

Таким образом, даже у вас есть три разных хэш-кода, вы получаете одно ведро для всех трех объектов, это означает сложность вашего HashMap O(n) вместо O(1).

Если мы применим функцию hash ко всем полученным хэш-кодам, получим

  • hash = 395, bucket = 395 % 20 = 15
  • hash = 3820, bucket = 3820 % 20 = 0
  • hash = 1577, bucket = 1577 % 20 = 17

Очистите, что, применяя hash в качестве дополнительного шага, мы получаем три разных ведра, которые сохраняют постоянный доступ времени к вашему объекту.

Ответ 3

оператор → > является битдвигом, но обрабатывается как unsigned.

^ - XOR (eXclusive или)

Итак, строка

h ^= (h >>> 20) ^ (h >>> 12);

означает xor оригинал с h бит-бит 20 бит, XOR с h сдвинутыми 12 бит

то

h ^ (h >>> 7) ^ (h >>> 4);

h сверху, xor h сдвинул 7 бит, xor h сдвинул 4 бита. Im не на 100% уверен, почему он настроен таким образом, хотя