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, doves[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?
RE la tua prima frase: hai visto qualche prova che la domanda o una particolare risposta stava assumendo xor? –
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) –
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. –