Функция хеш-кода

Моя функция хеш-кода для строки выглядит следующим образом

hashVal=(127*hashVal+key.charAt(i))%16908799

Я слежу за лекциями по cs61 b в Интернете, и я не совсем понимаю, когда профессор Джонатан говорит о том, что произойдет, если вместо 1690877 мы будем использовать значение, которое не является взаимно простым с 127. Я понимаю простой случай, когда он использует 127 вместо 16908799, но что, если бы это было простое кратное 127? Как это "искажает" хеш-значение? Как смещение зависит от общего множителя «х»? Может ли кто-нибудь предложить мне причину?


hashcode
person sreeprasad    schedule 25.09.2011    source источник

Ответы (1)


arrow_upward
6
arrow_downward

Используйте меньшие числа и подумайте об этом. Допустим, вы работаете в пространстве с модулем 10 (вместо 16908799). Тогда ваш hashVal может содержать только цифры 0-9.

Если вы умножите, например, на 7, то увидите, что можете получить все числа от 0 до 9:

(7*0)%10 = 0
(7*1)%10 = 7
(7*2)%10 = 4
(7*3)%10 = 1
(7*4)%10 = 8
(7*5)%10 = 5
(7*6)%10 = 2
(7*7)%10 = 9
(7*8)%10 = 6
(7*9)%10 = 3

Однако, если вы умножаете на 6 (что не является относительно простым с 10, потому что они имеют общий делитель 2), то вы не получите все числа 0-9, поэтому возникает смещение:

(6*0)%10 = 0
(6*1)%10 = 6
(6*2)%10 = 2
(6*3)%10 = 8
(6*4)%10 = 4
(6*5)%10 = 0
(6*6)%10 = 6
(6*7)%10 = 2
(6*8)%10 = 8
(6*9)%10 = 4
person jswolf19    schedule 25.09.2011