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

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 обозначает символ в строке, а п есть длина строки. Использование 16-битных Юникода, то первый символ из строки меня будет вычислен как:

87 X (31^34) 

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

Answer 1

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

/** 
* 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] 
* </pre></blockquote> 
* using <code>int</code> arithmetic, where <code>s[i]</code> is the 
* <i>i</i>th character of the string, <code>n</code> is the length of 
* the string, and <code>^</code> indicates exponentiation. 
* (The hash value of the empty string is zero.) 
* 
* @return a hash code value for this object. 
*/ 
public int hashCode() { 
    int h = hash; 
    int len = count; 
    if (h == 0 && len > 0) { 
     int off = offset; 
     char val[] = value; 
     for (int i = 0; i < len; i++) { 
      h = 31*h + val[off++]; 
     } 
     hash = h; 
    } 
    return h; 
} 

Answer 2

Большинство хеш-функции такого рода вычисления значения хэш-modulo некоторое большое число (например, большое простое число). Это позволяет избежать переполнения и сохраняет диапазон значений, возвращаемых функцией в указанном диапазоне. Но это также означает, что бесконечный диапазон входных значений получит хэш-значение из конечного набора возможных значений (т. Е. [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. Вы можете понять, почему он явно не использует модуль?