объясните пожалуйста этот код для вычисления хеш-кода строки

Question

Я прочитал книгу алгоритмов, в которой говорилось, что ключ данной строки вычисляется следующим образом

 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

с использованием int арифметики, где s [i] - i-й символ строки, n - длина строки, а ^ обозначает возведение в степень. (Значение хеша пустой строки равно нулю.)

или в коде:

 int h = 0;
 for (int i = 0; i < n; i++) {
   h = 31*h + s.charAt(i);
 }

Мой вопрос заключается в том, что, по-видимому, реализация кода не эквивалентна методу вычисления, указанному выше. Например, с учетом строки "ha" (коды ascii 104 и 97 соответственно)

с [0] * 31 ^ (2-1) + с [1] * 31 ^ 0 = 104 * 31 + 97

из кода выполнения, результат 104 + 31 * 104 + 97

абсолютно оба не равны, так как это объяснить?

Ссылка: http://www.informatics.sussex.ac.uk/courses/dats/notes/html/node114.html

Answer 1

Я думаю, что вы неправильно читаете код.

После первой итерации h равно 104.

Итак, вторая итерация говорит:

h = 31 * 104 + 97;

... это именно то, что вы ожидали.

Похоже, вы неправильно прочитали эту строку:

h = 31 * h + s.charAt(i);

как это:

h += 31 * h + s.charAt(i);

В данном коде мы не добавляем новое значение к h, мы используем простое присваивание.

Если вы на самом деле написали код и увидели неправильное значение, проверьте, есть ли у вас «+ =» вместо «=».

Answer 2

Вы можете сделать

int p = 1, h = 0;
for (int i = 0; i < n; i++)
{
    p *= 31;
    h += s.charAt(n - i - 1) * p;
}

чтобы код был понятным и таким же эффективным, как ваш.

В вашем коде используется схема Хорнера , и он верен, вы должны понять его на странице википедии выше.