Подтвердить что ты не робот

.Net GetHashcode Операция смены битов

Я просматривал некоторые из источника .net вчера и видел несколько реализаций GetHashcode с чем-то вроде этого:

(i1 << 5) + i ^ i2

Я понимаю, что делает код и почему. Я хочу знать, почему они использовали (i1 < 5) + я вместо (i1 < 5) - i.

Большинство фреймворков, которые я видел, используют -i, потому что это эквивалентно умножению на 31, что является простым, но способ Microsoft эквивалентен умножению на 33, который имеет 11 и 3 в качестве факторов и, следовательно, не является простым.

Есть ли известное обоснование для этого? Любые разумные гипотезы?

Ответ 1

Я задал тот же вопрос о math.stackexchange.com: Любопытные свойства из 33.

Гипотеза среди математиков и исследование, которое я сделал по этой теме, заставляют меня думать, что ответ таков:

Хорошо, я узнал, почему Microsoft использует 33. Это называется Bernstein Hash. Оказывается, что 33 имеет некоторые магические свойства, которые создают хорошее распределение хеш-кодов и очень мало теоретических знания о том, почему.

В принципе, при энтропии и сравнении скорости Бернштейн делает достаточно хорошо и довольно быстро. Дэн Бернштейн, парень, который придумал постоянную 33, не смог объяснить, какое свойство 33 создало такое хорошее распределение хешей.

Было написано несколько работ, сравнивающих хеш-функции и подтвердивших это открытие, не объяснив при этом пользы от использования 33. Кроме того, я не мог найти, почему Java использует 31 вместо этого. Кажется, это математическая и программирующая тайна на сегодняшний день.

Ответ 2

Я не помню, если 31 является одним из этих простых чисел, но есть некоторые простые числа, которые используются в качестве емкостей на Dictionary<K,V>. И если вы используете левое поле больше не влияет на выбранное ведро, а хэш вырождается.