Операция побитового сдвига .Net GetHashcode

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

(i1 << 5) + i ^ i2

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

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

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


.net bit-shift hashcode
person D. Patrick    schedule 10.08.2011    source источник
comment
Хорошо, я выяснил, почему Microsoft использует 33. Это называется хеш Бернштейна. Оказывается, число 33 обладает некоторыми волшебными свойствами, которые обеспечивают хорошее распределение хэш-кодов, и очень мало теоретических знаний о том, почему.   -  person D. Patrick    schedule 26.08.2011

Ответы (2)


arrow_upward
3
arrow_downward

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

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

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

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

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

person D. Patrick    schedule 05.10.2011

arrow_upward
0
arrow_downward

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

person CodesInChaos    schedule 10.08.2011
comment
31, похоже, не входит в список простых чисел для подсчета сегментов (смотря на System.Collections.HashHelpers.primes), но это не было моим вопросом в первую очередь. Мой вопрос: почему Microsoft умножает на 33, а не на 31? Другие фреймворки, которые я видел, умножают на 31. 33 даже не простое число. - person D. Patrick; 10.08.2011
comment
Если бы 31 появилось в этом списке, это объяснило бы, почему MS не использует 31 в качестве множителя. Но в любом случае быть премьером не так уж и важно. - person CodesInChaos; 10.08.2011