Perché Java hashCode () in String utilizza 31 come moltiplicatore?
Domanda
Secondo la documentazione Java, il il codice hash per un String
oggetto viene calcolato come:
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
usando
int
aritmetica, doves[i]
è il i th carattere della stringa,n
è la lunghezza di la stringa e^
indica l'espiazione.
Perché 31 viene utilizzato come moltiplicatore?
Comprendo che il moltiplicatore dovrebbe essere un numero primo relativamente grande. Quindi perché non 29, 37 o 97?
Soluzione
Secondo Java efficace di Joshua Bloch (un libro che non può essere abbastanza consigliato e che ho acquistato grazie alle continue menzioni su StackOverflow):
Il valore 31 è stato scelto perché è un numero primo dispari. Se fosse pari e la moltiplicazione traboccasse, le informazioni andrebbero perse, poiché la moltiplicazione per 2 equivale allo spostamento. Il vantaggio di usare un numero primo è meno chiaro, ma è tradizionale. Una bella proprietà di 31 è che la moltiplicazione può essere sostituita da uno spostamento e una sottrazione per prestazioni migliori:
31 * i == (i << 5) - i
. Le VM moderne eseguono questo tipo di ottimizzazione automaticamente.
(dal Capitolo 3, Articolo 9: Sostituisci sempre l'hashcode quando sostituisci uguale, pagina 48)
Altri suggerimenti
Come Goodrich e Tamassia indicano, se prendi più di 50.000 parole inglesi (formate come unione degli elenchi di parole forniti in due varianti di Unix), utilizzando le costanti 31, 33, 37, 39 e 41 produrrà meno di 7 collisioni in ciascun caso. Sapendo questo, non dovrebbe sorprendere che molte implementazioni Java scelgano una di queste costanti.
Per coincidenza, ero nel mezzo della lettura della sezione " codici hash polinomiali " quando ho visto questa domanda.
EDIT: ecco il link al libro PDF ~ 10mb di cui mi riferisco sopra. Vedere la sezione 10.2 Tabelle hash (pagina 413) di Strutture dati e algoritmi in Java
Su (principalmente) vecchi processori, moltiplicare per 31 può essere relativamente economico. Su un ARM, ad esempio, è solo un'istruzione:
RSB r1, r0, r0, ASL #5 ; r1 := - r0 + (r0<<5)
La maggior parte degli altri processori richiederebbe un turno separato e sottrarre istruzioni. Tuttavia, se il moltiplicatore è lento, questa è comunque una vittoria. I processori moderni tendono ad avere moltiplicatori veloci, quindi non fa molta differenza, fintanto che 32 va dalla parte giusta.
Non è un ottimo algoritmo di hash, ma è abbastanza buono e migliore del codice 1.0 (e molto meglio delle specifiche 1.0!).
Moltiplicando, i bit vengono spostati a sinistra. Questo utilizza più spazio disponibile dei codici hash, riducendo le collisioni.
Non usando una potenza di due, vengono popolati anche i bit più in basso a destra, da mescolare con il prossimo pezzo di dati che va nell'hash.
L'espressione n * 31
è equivalente a (n << 5) - n
.
Puoi leggere il ragionamento originale di Bloch sotto " Commenti " in http://bugs.java.com/bugdatabase/view_bug.do?bug_id = 4045622 . Ha studiato le prestazioni di diverse funzioni hash rispetto alla quot & Risultante; dimensione media della catena & Quot; in una tabella hash. P(31)
era una delle funzioni più comuni in quel periodo che trovò nel libro di K & amp; R (ma nemmeno Kernighan e Ritchie non ricordavano da dove provenisse). Alla fine ha dovuto sceglierne uno e quindi ha preso P(33)
dal momento che sembrava funzionare abbastanza bene. Anche se <=> non era davvero peggio e la moltiplicazione per 33 è ugualmente veloce da calcolare (solo uno spostamento di 5 e un'aggiunta), ha optato per 31 poiché 33 non è un numero primo:
Del rimanente quattro, probabilmente selezionerei P (31), poiché è il più economico da calcolare su un RISC macchina (perché 31 è la differenza di due potenze di due). P (33) è allo stesso modo economico da calcolare, ma le sue prestazioni sono leggermente peggiori, e 33 è composito, il che mi rende un po 'nervoso.
Quindi il ragionamento non era così razionale come molte delle risposte qui sembrano implicare. Ma siamo tutti bravi a trovare ragioni razionali dopo le decisioni dell'intestino (e anche Bloch potrebbe essere incline a questo).
In realtà, 37 funzionerebbe abbastanza bene! z: = 37 * x può essere calcolato come y := x + 8 * x; z := x + 4 * y
. Entrambi i passaggi corrispondono a una delle istruzioni LEA x86, quindi questo è estremamente veloce.
In effetti, la moltiplicazione con il primo ancora più grande 73 potrebbe essere eseguita alla stessa velocità impostando y := x + 8 * x; z := x + 8 * y
.
L'uso di 73 o 37 (anziché 31) potrebbe essere migliore, perché porta a codice più denso : le due istruzioni LEA richiedono solo 6 byte contro i 7 byte per spostamento + spostamento + sottrai per la moltiplicazione per 31. Un possibile avvertimento è che le istruzioni LEA a 3 argomenti utilizzate qui sono diventate più lente sull'architettura Intel Sandy Bridge, con una latenza aumentata di 3 cicli.
Inoltre, 73 è il numero preferito di Sheldon Cooper.
Neil Coffey spiega perché 31 viene utilizzato in Stiratura del polarizzazione .
Fondamentalmente l'uso di 31 ti dà una distribuzione di probabilità più omogenea per la funzione hash.
Da JDK-4045622 , in cui Joshua Bloch descrive i motivi perché è stata scelta quella particolare (nuova) String.hashCode()
implementazione
La tabella seguente riassume le prestazioni dei vari hash funzioni sopra descritte, per tre set di dati:
1) Tutte le parole e le frasi con voci in Merriam-Webster Dizionario non abbreviato internazionale (311.141 stringhe, lunghezza media 10 caratteri).
2) Tutte le stringhe in / bin / , / usr / bin / , / usr / lib / , / usr / ucb / e / usr / openwin / bin / * (66.304 stringhe, lunghezza media di 21 caratteri).
3) Un elenco di URL raccolti da un web crawler eseguito per diversi ore ieri sera (28.372 stringhe, lunghezza media 49 caratteri).
La metrica delle prestazioni mostrata nella tabella è la " dimensione media della catena " su tutti gli elementi nella tabella hash (ovvero, il valore atteso di numero di chiavi confronta per cercare un elemento).
Webster's Code Strings URLs --------- ------------ ---- Current Java Fn. 1.2509 1.2738 13.2560 P(37) [Java] 1.2508 1.2481 1.2454 P(65599) [Aho et al] 1.2490 1.2510 1.2450 P(31) [K+R] 1.2500 1.2488 1.2425 P(33) [Torek] 1.2500 1.2500 1.2453 Vo's Fn 1.2487 1.2471 1.2462 WAIS Fn 1.2497 1.2519 1.2452 Weinberger's Fn(MatPak) 6.5169 7.2142 30.6864 Weinberger's Fn(24) 1.3222 1.2791 1.9732 Weinberger's Fn(28) 1.2530 1.2506 1.2439
Guardando questa tabella, è chiaro che tutte le funzioni tranne l'attuale funzione Java e le due versioni non funzionanti di Weinberger la funzione offre prestazioni eccellenti, quasi indistinguibili. io congettura fortemente che questa prestazione sia essenzialmente la " ideale teorico " ;, che è quello che otterresti se usassi un vero casuale generatore di numeri al posto di una funzione hash.
Escluderei la funzione WAIS poiché le sue specifiche contengono pagine di numeri casuali e le sue prestazioni non sono migliori di nessuna delle funzioni molto più semplici. Qualsiasi delle restanti sei funzioni sembra scelte eccellenti, ma dobbiamo sceglierne una. Suppongo che escluderei La variante di Vo e la funzione di Weinberger a causa della loro aggiunta complessità, seppur minore. Dei restanti quattro, probabilmente selezionerei P (31), poiché è il più economico da calcolare su una macchina RISC (perché 31 è la differenza di due poteri di due). P (33) è altrettanto economico calcola, ma le sue prestazioni sono leggermente peggiori e 33 lo è composito, il che mi rende un po 'nervoso.
Josh
Non sono sicuro, ma immagino che abbiano testato alcuni campioni di numeri primi e scoperto che 31 ha dato la migliore distribuzione su alcuni campioni di possibili stringhe.
Bloch non si occupa proprio di questo, ma la logica che ho sempre sentito / creduto è che questa è algebra di base. Gli hash si riducono alle operazioni di moltiplicazione e modulo, il che significa che non puoi mai usare numeri con fattori comuni se puoi aiutarli. In altre parole, numeri relativamente primi forniscono una distribuzione uniforme delle risposte.
I numeri che compongono usando un hash sono in genere:
- modulo del tipo di dati in cui lo hai inserito (2 ^ 32 o 2 ^ 64)
- modulo del conteggio dei bucket nella tua hashtable (varia. In java era prima, ora 2 ^ n)
- moltiplica o sposta per un numero magico nella tua funzione di missaggio
- Il valore di input
Puoi davvero controllare solo un paio di questi valori, quindi è necessario un po 'di attenzione in più.
Nell'ultima versione di JDK, 31 è ancora usato. https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/String.html#hashCode ()
Lo scopo della stringa hash è
- unico (vedi operatore
^
nel documento di calcolo dell'hashcode, aiuta univoco) - costo economico per il calcolo
31 è il valore massimo che può essere inserito nel registro a 8 bit (= 1 byte). è il numero primo più grande che può essere inserito nel registro a 1 byte, è un numero dispari.
Moltiplica 31 è < < 5 quindi sottrae se stesso, quindi ha bisogno di risorse economiche.