Prueba: ¿por qué la implementación de java.lang.String.hashCode() coincide con su documentación?

Question

La documentación JDK para java.lang.String.hashCode()famously dice:

El código hash para un objeto String se calcula como

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

utilizando int aritmética, donde s[i] es el * i * º carácter de la cadena, n es la longitud de la cadena, y ^ indica exponenciación.

La implementación estándar de esta expresión es:

int hash = 0; 
for (int i = 0; i < length; i++) 
{ 
    hash = 31*hash + value[i]; 
} 
return hash; 

En cuanto a esto me hace sentir como si estuviera durmiendo a través de mi curso de algoritmos. ¿Cómo se traduce esa expresión matemática en el código de arriba?

Answer 1

No estoy seguro de si se olvidó de dónde dice "^ indica exponenciación" (no xor) en esa documentación.

Cada vez a través del bucle, el valor anterior de hash es multiplicada por 31 de nuevo antes de ser añadido al siguiente elemento de value.

pudo probar estas cosas son iguales por inducción, pero creo que un ejemplo podría ser más clara :

decir que estamos tratando con una cadena de 4-char.Vamos a desenrollar el bucle:

hash = 0; 
hash = 31 * hash + value[0]; 
hash = 31 * hash + value[1]; 
hash = 31 * hash + value[2]; 
hash = 31 * hash + value[3]; 

Ahora combinar estos en una declaración mediante la sustitución de cada valor de comprobación aleatoria, la siguiente declaración:

hash = 31 * (31 * (31 * (31 * 0 + value[0]) + value[1]) + value[2]) 
    + value[3]; 

31 * 0 es 0, por lo que simplifican:

hash = 31 * (31 * (31 * value[0] + value[1]) + value[2]) 
    + value[3]; 

Ahora multiplica los dos términos internos por ese segundo 31:

hash = 31 * (31 * 31 * value[0] + 31 * value[1] + value[2]) 
    + value[3]; 

Ahora multiplique los tres términos internos de ese primer 31:

hash = 31 * 31 * 31 * value[0] + 31 * 31 * value[1] + 31 * value[2] 
    + value[3]; 

y convertir a los exponentes (no es realmente más de Java):

hash = 31^3 * value[0] + 31^2 * value[1] + 31^1 * value[2] + value[3]; 

Answer 2

desenrollar el bucle. A continuación, se obtiene:

int hash = 0; 

hash = 31*hash + value[0]; 
hash = 31*hash + value[1]; 
hash = 31*hash + value[2]; 
hash = 31*hash + value[3]; 
... 
return hash; 

Ahora usted puede hacer alguna manipulación matemática, enchufe 0 para el valor hash inicial:

hash = 31*(31*(31*(31*0 + value[0]) + value[1]) + value[2]) + value[3])... 

simplificarlo un poco más:

hash = 31^3*value[0] + 31^2*value[1] + 31^1*value[2] + 31^0*value[3]... 

y que es esencialmente el algoritmo original dado.

Answer 3

Tome un vistazo a las primeras iteraciones y verá el inicio patrón a surgir:

 
hash0 = 0 + s0 = s0 
hash1 = 31(hash0) + s1 = 31(s0) + s1 
hash2 = 31(hash1) + s2 = 31(31(s0) + s1) + s2 = 312(s0) + 31(s1) + s2 
... 

Answer 4

demostración por inducción:

T1(s) = 0 if |s| == 0, else s[|s|-1] + 31*T(s[0..|s|-1]) 
T2(s) = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 
P(n) = for all strings s s.t. |s| = n, T1(s) = T2(s) 

Let s be an arbitrary string, and n=|s| 
Base case: n = 0 
    0 (additive identity, T2(s)) = 0 (T1(s)) 
    P(0) 
Suppose n > 0 
    T1(s) = s[n-1] + 31*T1(s[0:n-1]) 
    T2(s) = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] = s[n-1] + 31*(s[0]*31^(n-2) + s[1]*31^(n-3) + ... + s[n-2]) = s[n-1] + 31*T2(s[0:n-1]) 
    By the induction hypothesis, (P(n-1)), T1(s[0:n-1]) = T2(s[0:n-1]) so 
     s[n-1] + 31*T1(s[0..n-1]) = s[n-1] + T2(s[0:n-1]) 
    P(n) 

creo que lo tengo, y una prueba fué solicitado.

Answer 5

¿No es inútil en absoluto para contar el código hash de String out de todos los caracteres? Imagine nombres de archivos o nombres de clases con su ruta completa en HashSet. O alguien que utiliza HashSets de documentos String en lugar de Listas porque "HashSet always beats Lists".

Me gustaría hacer algo como:

int off = offset; 
char val[] = value; 
int len = count; 

int step = len <= 10 ? 1 : len/10; 

for (int i = 0; i < len; i+=step) { 
    h = 31*h + val[off+i]; 
} 
hash = h 

En el código hash final no es más que una pista.