Как вычислить хеш-код строки вручную?

Question

Мне было интересно, как вручную вычислить хеш-код для заданной строки.Я понимаю, что в Java вы можете сделать что-то вроде:

String me = "What you say what you say what?";  
long whatever = me.hashCode();

Это все хорошо и здорово, но мне было интересно, как это сделать вручную.Я знаю, что данная формула для вычисления хеш-кода строки выглядит примерно так:

S0 X 31 ^ (n-1) + S1 X 31 ^ (n-2) + .... + S(n-2) X 31 + S(n-1)  

Где S указывает символ в строке, а n - длина строки.Используя 16-битный Unicode, первый символ из строки me будет вычислен как:

87 X (31 ^ 34)

Однако это создает безумно большое число.Я не могу себе представить, как все персонажи складываются вместе.Итак, чтобы вычислить 32-битный результат самого низкого порядка, что я буду делать?Длинна, что бы ни было сверху равно -957986661, и я не как это рассчитать?

Answer 1

Посмотрите на исходный код java.lang.String.

<code>/**
 * Returns a hash code for this string. The hash code for a
 * <code>String</code> object is computed as
 * <blockquote><pre>
 * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
 * 

*, используя int арифметику, где s[i] - * i -й символ строки, n - это длина * строки, а ^ означает возведение в степень.* (Хеш-значение пустой строки равно нулю.) * * @ Вернуть значение хеш-кода для этого объекта.* / public int hashCode () {int h = hash;int len ​​= count;if (h == 0 && len> 0) {int off = offset;char val [] = значение;for (int i = 0; i

Answer 2

Большинство хеш-функций такого рода вычисляют хеш-значение по модулю некоторое большое число (например, большое простое число). Это позволяет избежать переполнений и сохраняет диапазон значений, возвращаемых функцией, в пределах указанного диапазона. Но это также означает, что бесконечный диапазон входных значений будет получать хеш-значение из конечного набора возможных значений (т. Е. [0, модуль)), поэтому возникает проблема коллизий хешей.

В этом случае код будет выглядеть примерно так:

   public int hash(String x){
        int hashcode=0;
        int MOD=10007;
        int shift=29;
        for(int i=0;i<x.length();i++){
            hashcode=((shift*hashcode)%MOD+x.charAt(i))%MOD;
        }
        return hashcode; 
    }

Упражнение для читателя:

См. Код функции hashCode для java.util.String. Вы понимаете, почему он не использует модуль явно?