Beweis: Warum stimmt die Implementierung von java.lang.String.hashCode() mit ihrer Dokumentation überein?

Question

Die JDK-Dokumentation für java.lang.String.hashCode()famously sagt:

Der Hash-Code für ein String-Objekt wird wie folgt berechnet

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

int Arithmetik, wo s[i] das ist * i * te Zeichen der Zeichenkette, n ist die Länge der Zeichenfolge und ^ zeigt die Potenzierung an.

Die Standardimplementierung dieses Ausdrucks ist:

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

Mit Blick auf das ich mich das Gefühl wie war meine Algorithmen natürlich schlafen durch. Wie übersetzt sich dieser mathematische Ausdruck in den obigen Code?

Answer 1

Ich bin nicht sicher, wenn Sie verpasst haben, wo es heißt "^ zeigt Exponentiation" (nicht xor) in dieser Dokumentation.

Jedes Mal durch die Schleife, wird der vorherige Wert des Hash von 31 multipled wieder, bevor zum nächsten Element der value hinzugefügt wird.

Man könnte diese Dinge sind gleich durch Induktion beweisen, aber ich denke, ein Beispiel könnte mehr klar sein:

sagen wir mit einem 4-char-String zu tun hat.Lassen Sie uns die Schleife entrollen:

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

Und dies in einer Anweisung kombinieren, indem jeder Wert von Hash in die folgende Anweisung ersetzt:

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

31 * 0 0, so vereinfachen:

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

Jetzt multiplizieren Sie die beiden inneren Terme mit dieser Sekunde 31:

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

nun die drei inneren Bedingungen durch diesen ersten 31 multiplizieren:

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

und konvertieren Exponenten (nicht wirklich Java mehr):

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

Answer 2

die Schleife ausrollen. Dann erhalten Sie:

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; 

Jetzt können Sie einige mathematische Manipulation tun, stecken Sie in 0 für den Anfangs-Hash-Wert:

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

Vereinfachen es etwas mehr:

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

Und das ist im Wesentlichen der ursprüngliche Algorithmus gegeben.

Answer 3

Werfen Sie einen Blick auf die ersten paar Iterationen und Sie werden das Musterstart sehen aufzutauchen:

 
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

Beweis durch Induktion:

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) 

Ich glaube, ich habe es, und einen Beweis wurde ersucht.

Answer 5

Ist es nicht nutzlos an alle hashcode zählen der String aus aller Zeichen? Stellen Sie sich Dateinamen oder Klassennamen mit ihrem vollständigen Pfad in HashSet vor. Oder jemand, der HashSets von String-Dokumenten anstelle von Listen verwendet, weil "HashSet always beats Lists".

ich tun würde, so etwas wie:

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 

Am Ende hashcode ist nichts anderes als ein Hinweis.