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

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

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

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

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

a * 31 + b

Настоящая проблема проявляется, когда в формуле много элементов.

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

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

31 ^ 7 > Integer.MAX_VALUE

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

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

ИЗМЕНИТЬ

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 битами, тогда значение было бы другим.


algorithm hashcode
person mP.    schedule 10.02.2011    source источник

Ответы (3)


arrow_upward
3
arrow_downward

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

person Jeremiah Willcock    schedule 10.02.2011
comment
Да, но со временем в хэш-коде фактически присутствуют только самые младшие биты. - person mP.; 10.02.2011
comment
@mP: Что ты имеешь в виду? Все входные элементы влияют на окончательный хэш-код, когда вы используете нечетный множитель. - person Jeremiah Willcock; 10.02.2011
comment
@Jeremiah, я ответил в своем исходном вопросе с некоторыми математическими расчетами и примерами моего pt. - person mP.; 10.02.2011
comment
@mP: я не вижу новых правок в вашем вопросе. Возможно, вам придется попробовать код, чтобы увидеть, как он себя ведет. Просто напишите функцию, которая делает то, что вы показываете в своем вопросе, и протестируйте ее на строках с разным началом, но одинаковым концом. Если вы используете что-то вроде 31 в качестве константы, хеш-коды будут меняться независимо от того, какую часть строки вы изменяете. - person Jeremiah Willcock; 10.02.2011
comment
@JW проверьте наличие EDIT, выделенного жирным шрифтом, вы увидите, что цифры демонстрируют, как старшие биты в конечном итоге теряются из-за умножения. Я мог бы попытаться придумать пример в коде, но приведенной выше математики должно быть достаточно. - person mP.; 10.02.2011
comment
@mP: Эти биты в конечном итоге теряются или теряются сразу? Это правда, что если вы используете большие числа в качестве входных данных для хэш-кода, они не будут иметь большого эффекта, но это не изменится, если вы впоследствии добавите больше чисел (попробуйте тот же пример с различными степенями 31, и он будет вести себя аналогично). ). Однако если вы хешируете строки, проблема, которую вы показываете, не появится. - person Jeremiah Willcock; 10.02.2011
comment
@JW Я думаю, в конце концов или, возможно, раньше, не давая точных определений этих терминов. - person mP.; 11.02.2011

arrow_upward
2
arrow_downward

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

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

person jason    schedule 10.02.2011
comment
Мало того, что давно бы столкнулся с такой же проблемой, просто взял бы немного longер. (извините, это было плохо...) - person corsiKa; 10.02.2011
comment
Вся причина использования простых чисел в качестве множителя заключается в том, что шансы означают, что значения сдвигаются влево, и в конечном итоге все биты теряются. Однако у простых чисел все еще есть та же проблема, они просто немного лучше, и для исчезновения битов требуется больше времени. - person mP.; 11.02.2011

arrow_upward
0
arrow_downward

Не вижу смысла в примерах. Мне кажется, они не связаны с тем, как вы вычисляете хеш-коды: 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 в двоичном формате этого не произойдет.

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

person Ishtar    schedule 10.02.2011
comment
Первая часть довольно плохо пыталась продемонстрировать, как биты переполняются и исчезают при умножении. Ваш комментарий о 65536 совершенно верен. Приведенные выше расчеты показывают, что биты высокого порядка теряются довольно быстро, поэтому, если первый член имеет хэш-код 0x10001 или 0x30001, 0x70001 или 0xffff0001 быстро теряются. - person mP.; 11.02.2011
comment
Мои комментарии пытались указать, что акт умножения вводит 0 бит, которые можно заменить некоторыми подходящими единицами, если переполнение не будет проигнорировано. - person mP.; 11.02.2011
comment
@mP - Вы правы насчет умножения. Но ваш вопрос касается распространения хэш-кода, верно? Хорошее распределение и потеря старших битов не связаны между собой, если вы используете 31, а не 65536. - person Ishtar; 11.02.2011
comment
использование 65536, что фактически является сдвигом на 16, показывает, что проблема лучше всего выделяется. Умножение на 31 n раз также сдвигает младшие биты до тех пор, пока они не переполнятся. - person mP.; 04.06.2012