Perché Java hashCode () in String utilizza 31 come moltiplicatore?

Question

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, dove s[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?

Answer 1

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)

Answer 2

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

Answer 3

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!).

Answer 4

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.

Answer 5

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).

Answer 6

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.

Answer 7

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.

Answer 8

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

Answer 9

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.

Answer 10

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ù.

Answer 11

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.