.Net GetHashcode Bit Shifting Операция

Question

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

(i1 << 5) + i ^ i2

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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