Preuve: pourquoi l'implémentation de java.lang.String.hashCode () correspond-elle à sa documentation?

Question

La documentation JDK pour < code> java.lang.String.hashCode () de manière célèbre dit:

  

Le code de hachage d'un objet String est calculé comme suit:

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

     

en utilisant l'arithmétique int , où s [i] est le * i * ème caractère de la chaîne, n est la longueur de la chaîne et ^ indique une exponentiation.

L'implémentation standard de cette expression est:

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

En regardant cela, je me sens comme si je dormais dans le cadre de mon cours sur les algorithmes. Comment cette expression mathématique se traduit-elle dans le code ci-dessus?

Answer 1

Je ne sais pas si vous avez omis de mentionner "& indique; ^ indique une exponentiation". (pas xor) dans cette documentation.

Chaque fois dans la boucle, la valeur précédente de hash est multipliée par 31 à nouveau avant d'être ajoutée à l'élément suivant de valeur .

On pourrait prouver que ces choses sont égales par induction, mais je pense qu'un exemple pourrait être plus clair:

Disons que nous avons affaire à une chaîne de 4 caractères. Déroulons la boucle:

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

Combinez maintenant ces éléments dans une instruction en substituant chaque valeur de hachage à l'instruction suivante:

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

31 * 0 est 0, alors simplifiez-vous:

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

Maintenant, multipliez les deux termes internes par cette seconde 31:

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

Maintenant, multipliez les trois termes internes par ce premier 31:

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

et convertir en exposants (plus vraiment Java):

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

Answer 2

déroulez la boucle. Ensuite, vous obtenez:

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;

Vous pouvez maintenant faire quelques manipulations mathématiques, insérez 0 pour la valeur de hachage initiale:

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

Simplifiez-le un peu plus:

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

Et c’est essentiellement l’algorithme original donné.

Answer 3

Preuve par induction:

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)

Je pense l'avoir et une preuve a été demandée.

Answer 4

Jetez un coup d’œil aux premières itérations et vous verrez que le motif commence à se dessiner:

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 5

N'est-il pas inutile de compter le hashcode de la chaîne de tous les caractères ? Imaginez des noms de fichier ou des noms de classe avec leur chemin complet placé dans HashSet. Ou quelqu'un qui utilise des documents HashSets of String au lieu de Lists car " HashSet bat toujours les listes " .

Je voudrais faire quelque chose comme:

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

À la fin, le hashcode n’est rien d’autre qu’un indice.