Хеширование строк в Java

Question

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

Ну это полный код:

long sfold(String s, int M) { 
int intLength = s.length()/4; 
long sum = 0; 
for (int j = 0; j < intLength; j++) { 
    char c[] = s.substring(j * 4, (j * 4) + 4).toCharArray(); 
    long mult = 1; 
    for (int k = 0; k < c.length; k++) { 
sum += c[k] * mult; 
mult *= 256; 
    } 
} 

char c[] = s.substring(intLength * 4).toCharArray(); 
long mult = 1; 
for (int k = 0; k < c.length; k++) { 
    sum += c[k] * mult; 
    mult *= 256; 
} 

return(Math.abs(sum) % M); 

}

Здесь каждый символьное значение преобразуется в длинное целое типа, подводя результат на каждой итерации для цикла. Эти 2 сомнительные строки кода, которые я уже упоминал выше, являются следующие:

sum += c[k] * mult; 
mult *= 256; 

Ну, я могу понять весь код, за исключением этих 2-х линий ...

1) Почему нам нужна переменная «Mult» ? Возможно ли это использование метода умножения для хеширования?

2) Почему мы умножаем «мульти» точно на 256 на каждой итерации? Что такое 256 в этом случае?

Если некоторые из вас сталкивались с этим кодом, или вы знаете, идея, которая выполняется в этих строках, пожалуйста, помогите мне понять это тоже :)

Answer 1

Из-за того, что c[k] является обугливается имеет размер из 8 бит и 8 бит - это точно 256 возможных чисел. Так, например, у нас есть char[] c = new char[]{'a, 'b', 'c', 'd'}, здесь 'a' в немного мудрой форме будет выглядеть примерно как 10000001 и b что-то вроде 10000010 и так далее. Теперь вопрос заключается в том, как мы формируем sum, во-первых, мы просто принимаем наше представление a по-бит, поэтому sum становится 10000001, затем мы берем b в битовой форме и умножаем его на 256, что на самом деле является просто битным сдвигом на 8 бит до влево, это означает, что 'b' * 256 совпадает с 10000001 * 100000000 = 1000000100000000 (256 в битовой форме 100000000), и теперь, когда мы добавляем это 'b' * 256 с предыдущей суммой, это означает просто подставить последние 8 бит битовой формой a. То же самое происходит и дальше.

Итак, в итоге мы просто получаем число, которое является мутным сцеплением наших предыдущих char s (например, 10000001 10000010 10000011 10000100).

Я надеюсь, что это поможет.

Answer 2

Умножение на 256 фактически сдвигает биты влево на 8 позиций (1 байт).

Итак, что это делает:

• он хранит биты первого символа в нижних 8 бит (первый байт),
• следующего символа 8 бит в следующих 8 позиций (следующий байт) и т. д., до четырех.

Я приведу пример для 4-битной системы (мы умножаем на 16 в этом случае):

c[0] = 1101 
c[1] = 1001 
c[2] = 0010 
c[3] = 0110 

он строит long сумму биты которого выглядит следующим образом:

0110 0010 1001 1101 
c[3] c[2] c[1] c[0] 

Answer 3

Код в основном идет один byte за раз. Каждый байт имеет 8 бит или номер 256. Другими словами, умножение на 256 подобно сдвигу значения влево на один байт.