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

In Java, il codice hash per un object String è calcolato come

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

usando l’aritmetica int , dove s[i] è il carattere iimo della stringa, n è la lunghezza della stringa e ^ indica l’esponenziazione.

Perché 31 è usato come moltiplicatore?

Capisco che il moltiplicatore dovrebbe essere un numero primo relativamente grande. Allora perché non 29, o 37, o anche 97?

Secondo Joshua Bloch’s Effective Java (un libro che non può essere raccomandato abbastanza, e che ho comprato grazie a continue menzioni sullo 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 utilizzare un 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 moderne macchine virtuali eseguono automaticamente questo tipo di ottimizzazione.

(dal Capitolo 3, Articolo 9: Sostituisci sempre hashcode quando si esegue l'override su uguali, pagina 48)

Come sottolineano Goodrich e Tamassia , se prendi oltre 50.000 parole inglesi (formate come unione delle liste di parole fornite in due varianti di Unix), l’uso delle costanti 31, 33, 37, 39 e 41 produrrà meno di 7 collisioni in ogni caso. Sapendo questo, non dovrebbe sorprendere che molte implementazioni Java scelgano una di queste costanti.

Per coincidenza, stavo leggendo la sezione “codici di hash polinomiali” quando ho visto questa domanda.

EDIT: ecco il link al libro in formato PDF da ~ 10mb di cui mi riferisco sopra. Vedere la sezione 10.2 Tabelle hash (pagina 413) di Strutture dati e Algoritmi in Java

Su (soprattutto) vecchi processori, moltiplicando per 31 può essere relativamente economico. Su un ARM, per esempio, è solo una istruzione:

 RSB r1, r0, r0, ASL #5 ; r1 := - r0 + (r0< <5) 

La maggior parte degli altri processori richiederebbe istruzioni di spostamento e sottrazione separate. Tuttavia, se il tuo moltiplicatore è lento, è comunque una vittoria. I processori moderni tendono ad avere moltiplicatori veloci quindi non fa molta differenza, a patto che il 32 vada sul lato corretto.

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 sono spostati a sinistra. Questo utilizza più dello spazio disponibile dei codici hash, riducendo le collisioni.

Non usando una potenza di due, vengono popolati anche i bit più a destra, più bassi, da mescolare con il prossimo pezzo di dati che entra 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 esaminato le prestazioni di diverse funzioni hash in relazione alla “dimensione media della catena” risultante in una tabella hash. P(31) era una delle funzioni comuni durante quel periodo che trovò nel libro di K & R (ma anche Kernighan e Ritchie non riuscivano a ricordare da dove venisse). Alla fine ha dovuto sceglierne uno e quindi ha preso P(31) poiché sembrava funzionare abbastanza bene. Anche se P(33) non era molto peggio e la moltiplicazione per 33 è altrettanto veloce da calcolare (solo uno spostamento per 5 e un’aggiunta), ha optato per 31 poiché 33 non è un numero primo:

Dei rimanenti quattro, probabilmente selezionerei P (31), poiché è il più economico da calcolare su una macchina RISC (perché 31 è la differenza tra due potenze di due). P (33) è altrettanto economico da calcolare, ma le prestazioni sono marginalmente 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 ragionare con ragioni razionali dopo le decisioni di budello (e anche Bloch potrebbe essere incline a questo).

In realtà, 37 funzionerebbe piuttosto bene! z: = 37 * x può essere calcolato come y := x + 8 * x; z := x + 4 * y y := x + 8 * x; z := x + 4 * y . Entrambi i passaggi corrispondono a una LEA x86 istruzioni, quindi questo è estremamente veloce.

In effetti, la moltiplicazione con il primo 73 ancora più grande potrebbe essere fatta alla stessa velocità impostando y := x + 8 * x; z := x + 8 * y y := x + 8 * x; z := x + 8 * y .

Usare 73 o 37 (anziché 31) potrebbe essere migliore, perché porta a un codice più denso : le due istruzioni LEA prendono solo 6 byte contro i 7 byte per spostare + maiusc + sottrarre per la moltiplicazione per 31. Un ansible avvertimento è che le istruzioni LEA a 3 argomenti utilizzate qui sono diventate più lente nell’architettura Sandy bridge di Intel, con una latenza aumentata di 3 cicli.

Inoltre, 73 è il numero preferito di Sheldon Cooper.

Neil Coffey spiega perché il 31 viene usato per Stirare il pregiudizio .

Fondamentalmente l’utilizzo di 31 offre una distribuzione di probabilità set-bit più uniforms per la funzione hash.

Non ne sono sicuro, ma suppongo che abbiano provato alcuni esempi di numeri primi e che 31 abbiano fornito la migliore distribuzione su un campione di possibili stringhe.

Bloch non si addentra in questo, ma la logica che ho sempre sentito / creduto è che questa è un’algebra di base. I hash si riducono a operazioni di moltiplicazione e modulo, il che significa che non si desidera mai utilizzare i numeri con fattori comuni se è ansible aiutarli. In altre parole, numeri relativamente primi forniscono una distribuzione uniforms delle risposte.

I numeri che compongono utilizzando un hash sono in genere:

  • modulo del tipo di dati in cui lo inserisci (2 ^ 32 o 2 ^ 64)
  • modulo del conteggio del bucket nel tuo hashtable (varia. In java usato come primo, ora 2 ^ n)
  • moltiplicare o spostare di un numero magico nella tua funzione di missaggio
  • Il valore di input

Sei in grado di controllare solo un paio di questi valori, quindi è necessario un minimo di attenzione.

Da JDK-4045622 , dove Joshua Bloch descrive le ragioni per cui è stata scelta quella particolare (nuova String.hashCode() implementazione di String.hashCode()

La tabella seguente riepiloga le prestazioni delle varie funzioni hash descritte sopra, per tre set di dati:

1) Tutte le parole e le frasi con le voci in Merriam-Webster’s 2nd Int’l Unabridged Dictionary (311.141 archi, 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 21 caratteri).

3) Un elenco di URL raccolti da un web crawler che è stato pubblicato per diverse ore la scorsa notte (28.372 stringhe, avg lunghezza 49 caratteri).

La metrica delle prestazioni mostrata nella tabella è la “dimensione media della catena” su tutti gli elementi nella tabella hash (cioè, il valore atteso del 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 la funzione Java corrente e le due versioni non funzionanti della funzione di Weinberger offrono prestazioni eccellenti, quasi indistinguibili. Propongo fortemente che questa performance sia essenzialmente l ‘”ideale teorico”, che è ciò che otterresti se usassi un vero generatore di numeri casuali al posto di una funzione di hash.

Escluderei la funzione WAIS in quanto le sue specifiche contengono pagine di numeri casuali e le sue prestazioni non sono migliori di nessuna delle funzioni più semplici. Qualunque delle restanti sei funzioni sembrano scelte eccellenti, ma dobbiamo sceglierne una. Suppongo che escluderei la variante di Vo e la funzione di Weinberger a causa della loro maggiore complessità, anche se minore. Dei rimanenti quattro, probabilmente selezionerei P (31), poiché è il più economico da calcolare su una macchina RISC (perché 31 è la differenza tra due potenze di due). P (33) è altrettanto economico da calcolare, ma le prestazioni sono marginalmente peggiori, e 33 è composito, il che mi rende un po ‘nervoso.

Josh