Расчет хеш-кода, зачем умножать и игнорировать переполнение битов?

Question

Этот вопрос не о том, почему умножается, это довольно очевидно - речь идет о распределении.

Зачем использовать простое число в hashCode?

А скорее эточем больше свойство умножения становится тем важнее, чем больше факторов включается в формулу вычисления хэш-кода.

Очевидно, что простое вычисление может быть переполнено, но это не имеет большого значения.

a * 31 + b

Реальная проблема проявляется, когда многие элементы находятся в формуле.

((a * 31) + b) * 31 ... 6n.

После включения более 5 или 6 терминов значение первого теряется, поскольку его биты переполняются к тому времени, когда значение хэш-кодадо включения 5+ срок.При использовании этой системы только последние 5 или около того терминов действительно вносят существенный вклад в конечное значение.

31 ^ 7 > Integer.MAX_VALUE

Так почему же большинство вычислений не переворачивают биты, которые переполняются, и возвращают xor с младшими битами результата,Я ценю, что для этого нужно немного поиграть, а вычисления должны выполняться с использованием длинных (64 бита), так что старшие 32 бита могут быть XOR с целочисленным результатом, но по крайней мере ни один бит не будет потерян.

IsЕсть ли какая-то конкретная причина, по которой переполнение игнорируется?Использование long не так уж и дорого, как описано ранее.

EDIT

100000*31^7=            2751261411100000       0x9C641F717C560
6553600000*31^7 180306667837849600000    0xC641F717C5600000

Обратите внимание, что последнее значение в 65536 раз больше, чем предыдущее, что также означаетчто его ответ на 16 бит больше.Обратите внимание, что целочисленное значение 0xC641F717C5600000 равно 0xC5600000, фактические значимые значения теряются из 16-битного значения.

*SAMPLE A*
65536*4096*27512614111  

=7385361114638319616
=0x667E12CDF0000000
   12345678
=0xF0000000

*SAMPLE B*
9*65536*4096*27512614111

=66468250031744876544
=0x9A6EA93D70000000
   12345678
=0x70000000

Обратите внимание, что самый старший бит SAMPLE B , что в точности равно 9x SAMPLE A практически не делает разницы в конечном 32-битном значении - если я изменил 9x на 17x, то младшие биты будут идентичны.Однако, если самые верхние биты не были «потеряны» из-за переполнения и xord с младшими 32 битами, тогда значение будет другим.

Answer 1

Это выгода от умножения на нечетное число; более ранние числа никогда не опускаются до конца целого числа полностью. Чтобы элемент был потерян, 31^n должно быть степенью 2, а этого не может быть. В вашем случае, например, с 31^7 вы получите 0x67E12CDF для 32-битного числа; таким образом, элемент ввода, умноженный на это значение, все равно будет влиять на результат, несмотря на переполнение.

Answer 2

Есть ли какая-то особая причина, по которой переполнение игнорируется? Использование long не так дорого, как описано ранее.

Но от этого почти наверняка нет выгоды. Эта методология обычно дает хорошее распределение значений для начала.

Answer 3

Я не вижу смысла в примерах. Они кажутся мне не связанными с тем, как вы вычисляете хеш-коды: a * 31 + b.

Возможно, вы могли бы найти a и b, которые дали бы тот же хэш-код (но где старшие биты разные). Тогда имело бы смысл переписать старшие биты обратно в хеш-код.

Или другой пример был бы для ((a * 31) + b )*31 + ... + z. Затем найдите некоторые a, b, ..., z, где хеш-код больше не зависит от a. Так что a не будет значительным вкладчиком.

Конечно, если вы измените 31 на 65536, найти эти a, ..., z довольно легко. Подойдет любое значение, все a бит просто упадут, a сдвинется влево и обрезается. Но вы можете сделать это для 31? Или подобным образом, вы могли бы снова записать старшие биты. Но почему? Можете ли вы найти случай, когда это поможет?

Проблема с 65536 состоит в том, что в двоичном виде это выглядит так 10000000000000000. Таким образом, когда вы умножаете число на него, в двоичном виде у него снова будут эти 16 нулей. Для 31, 11111 в двоичном формате этого не произойдет.

О, я не имею в виду, что эти примеры не существуют, потому что они существуют (в конце концов, это просто хэш). Но вы не найдете много или похожих примеров.