2009-05-04 3 views
9

La documentazione JDK per java.lang.String.hashCode()famously dice:Dimostrazione: perché l'implementazione di java.lang.String.hashCode() corrisponde alla sua documentazione?

il codice hash per un oggetto String è calcolata come

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

usando int aritmetica, dove s[i] è la * i * esimo carattere della stringa, n corrisponde alla lunghezza della stringa e ^ indica il valore di esponenziazione.

L'implementazione standard di questa espressione è:

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

Guardando questo mi fa sentire come stavo dormendo con mio corso algoritmi. Come si traduce questa espressione matematica nel codice sopra?

risposta

12

Non sono sicuro di aver dimenticato dove dice "^ indica l'esponenziazione" (non xor) in quella documentazione.

ogni iterazione del ciclo, il valore precedente di hash è moltiplicato per 31 nuovo prima di essere aggiunti al successivo elemento di value.

Si potrebbe dimostrare queste cose sono uguali per induzione, ma penso che un esempio potrebbe essere più chiaro :

Dire abbiamo a che fare con una stringa di 4 char.Facciamo Srotolare il ciclo:

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

ora combinare questi in una dichiarazione sostituendo ogni valore di hash nella seguente dichiarazione:

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

31 * 0 è 0, in modo da semplificare:

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

Ora moltiplicare i due termini interni per quel secondo 31:

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

Ora moltiplicare i tre termini interiori da quel primo 31:

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

e convertire a esponenti (non proprio Java più):

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

RE la tua prima frase: hai visto qualche prova che la domanda o una particolare risposta stava assumendo xor? –

+0

Hai espresso confusione su come il codice e la documentazione potrebbero essere equivalenti. Dal momento che la documentazione utilizzava "^" per l'esponenziazione, ma Java normalmente la usa per significare bit xor mi chiedevo se fosse questa la fonte della tua confusione. (Non ci sono state altre risposte quando ho iniziato a scrivere la mia risposta, BTW) –

+0

Ah, capisco. No, ero consapevole del fatto che si trattava di esponenziazione, ma non chiaro come l'implementazione sia stata seguita dall'espressione matematica. La tua risposta lo chiarisce molto - ma sapere di scrivere quel codice dato solo quell'espressione è ancora un salto per me. Per arrivare a quel codice, sembrerebbe che dovresti scrivere un piccolo esempio, rendersi conto che puoi "moltiplicare per 0 in modo intelligente" nell'incastramento più interno per completare il modello, quindi formare il ciclo. –

24

srotolare il ciclo. Quindi si ottiene:

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; 

ora si può fare un po 'di manipolazione matematica, collegare 0 per il valore hash iniziale:

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

semplificare un po' di più:

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

e che è essenzialmente l'algoritmo originale dato.

+0

Si consiglia di spiegarlo in termini di modulo statico single assignment (SSA), che elimina quindi la necessità di pensare a quale valore "hash" ha in un dato momento. :-) –

+0

Sembra che l'algoritmo originale dice che dovrebbe essere: 31^3 * valore [0] + 31^2 * valore [1] + 31^1 * valore [2] + ... Oppure è solo il mio cervello fritto ha sbagliato? – Adnan

+0

In realtà, sei corretto, farò la modifica. – CookieOfFortune

9

Date un'occhiata alle prime iterazioni e vedrete l'inizio modello ad emergere:

 
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 
... 
+1

<3 Grazie per (più o meno) la risposta di CookieOfFortune in formato SSA. Molto apprezzato! –

+0

Come si fanno gli abbonati? – CookieOfFortune

+0

Sarebbe ancora meglio se fosse possibile allineare verticalmente tutti i termini corrispondenti e distribuire il 31 (...) nella terza riga. –

10

Dimostrazione per induzione:

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) 

credo di avere, e una prova è stato richiesto

+1

oh scatto! Induzione! –

0

Non è inutile a tutti di contare il codice hash della stringa fuori di tutti i caratteri? Immagina nomi di file o nomi di classe con il loro percorso completo inserito in HashSet. O qualcuno che utilizza HashSet di documenti String anziché Elenchi perché "HashSet always beats Lists".

vorrei fare qualcosa di simile:

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 

Alla fine codice hash non è altro che un suggerimento.

+0

Ignorare la metà dei caratteri nella stringa significherebbe che memorizzare una sequenza di "conteggi di stringhe" in una tabella hash potrebbe facilmente causare il mapping di 100 stringhe a ciascun valore di hash. Ignorare più della metà dei personaggi renderebbe le cose ancora peggiori.Ignorare qualsiasi aspetto della stringa ai fini dell'hash rischia una penalità davvero enorme in cambio di un payoff piuttosto ridotto. – supercat

+0

Questo è essenzialmente ciò che i primi designer di Java però. Inizialmente, la funzione hash della stringa richiedeva solo un campione di caratteri quando la stringa era più lunga di 15 caratteri. Alla fine è stato necessario correggere perché si è rivelato che produceva prestazioni hash pessime con determinate stringhe (ad esempio con set di URL che spesso appaiono simili): http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622 . I guadagni in termini di prestazioni per non utilizzare l'intera stringa non possono compensare le prestazioni hash peggiori. –

+0

Per chiarire: il secondo tipo di prestazioni se si fa riferimento alle prestazioni della "tabella hash", non alla velocità non elaborata del calcolo dell'hash. –

Problemi correlati