Is String.hashCode() è inefficiente?

Question

Se si guarda alla source code of java.lang.String of openjdk-1.6, ho visto che String.hashCode() utilizza 31 come numero primo e calcola

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

Ora, la ragione per me di guardare a questo è stata la domanda che avevo in mente se si confrontano i codici hash in String.equals renderebbe String.equals notevolmente più veloce. Ma guardando hashCode ora, le seguenti domande mi vengono in mente:

• Non sarebbe un più grande primo contribuire ad evitare collisioni meglio, almeno per brevi stringhe, visto che per esempio "BC" ha lo stesso hash come " Ab "(dal momento che le lettere ascii vivono nella regione 65-122, un primo più alto di quello funziona meglio)?
• È una decisione consapevole utilizzare 31 come primo, o solo uno casuale che viene utilizzato perché è comune?
• Quanto è probabile una collisione di hash, data una lunghezza di stringa fissa? dove questa domanda sta andando è la domanda iniziale su come il confronto tra hashCode e lunghezza String potrebbe già distinguere le stringhe, per evitare di confrontare i contenuti effettivi.
• un po 'fuori tema, forse: c'è una buona ragione per cui String.equals non confronta hashCode come scorciatoia aggiuntiva?
• un po 'più fuori tema: supponendo di avere due stringhe con lo stesso contenuto di, ma diverse istanze: esiste un modo per affermare l'uguaglianza senza effettivamente confrontare i contenuti? Immagino di no, dato che in qualche modo nelle lunghezze delle Stringhe, lo spazio esplode in dimensioni dove inevitabilmente avremo collisioni, ma per quanto riguarda alcune restrizioni - solo un certo set di caratteri, una lunghezza massima della corda ... e quanto dobbiamo limitare lo spazio stringa per essere in grado di avere una tale funzione hash?

Answer 1

Non sarebbe un più grande primo contribuire ad evitare collisioni meglio, almeno per brevi stringhe, visto che per esempio "BC" ha lo stesso hash come "Ab" (dal momento che le lettere ASCII vivono nella regione 65 -122, un primo non più alto di quello funziona meglio)?

Ogni carattere in una stringa può assumere 65536 valori (2^16). L'insieme di stringhe di 1 o 2 caratteri è quindi più grande del numero di int e qualsiasi metodologia di calcolo hashcode produrrà collisioni per stringhe lunghe 1 o 2 caratteri (che si suppone come stringhe corte suppongo).

Se si limita il set di caratteri, è possibile trovare la funzione di hash che riducono il numero di collisioni (vedi sotto).

Si noti che un buon hash deve anche fornire una buona distribuzione dell'output. Un commento sepolto in this code incoraggia l'utilizzo di 33 e fornisce la seguente motivazione (sottolineatura mia):

Se si confrontano le chi^2 valori [...] delle varianti del numero 33 non ha nemmeno il miglior valore. Ma il numero 33 e pochi altri numeri ugualmente buoni come 17, 31, 63, 127 e 129 hanno comunque un grande vantaggio per i restanti numeri nel grande insieme di possibili moltiplicatori: la loro operazione di moltiplicazione può essere sostituita da un'operazione più veloce basata su solo un turno più una singola operazione di addizione o sottrazione. E perché una funzione hash deve sia distribuire bene che deve essere molto veloce da calcolare, quei pochi numeri dovrebbero essere preferiti.

Ora queste formule sono state progettate qualche tempo fa.Anche se apparisse ora che non sono ideali, sarebbe impossibile cambiare l'implementazione perché è documentata nel contratto della classe String.

È una decisione consapevole utilizzare 31 come primo, o solo uno casuale che viene utilizzato perché è comune?

Why does Java's hashCode() in String use 31 as a multiplier?

Come probabilmente è una collisione hash, data una lunghezza di stringa fissa?

Supponendo che ogni possibile valore int abbia la stessa probabilità di essere il risultato della funzione hashcode, la probabilità di collisione è 1 in 2^32.

C'è una buona ragione che String.equals non confronta hashCode come collegamento aggiuntivo?

Why does the equals method in String not use hash?

Supponendo che abbiamo due stringhe con lo stesso contenuto, ma istanze diverse: c'è un modo per affermare l'uguaglianza senza realmente confrontare il contenuto?

Senza alcun vincolo sulla stringa, non c'è. È possibile internare le stringhe quindi controllare l'uguaglianza di riferimento (==), ma se sono coinvolte molte stringhe, ciò può risultare inefficiente.

quanto è necessario limitare lo spazio della stringa per poter avere una tale funzione di hash?

Se si consente solo lettere small cap (26 caratteri), si potrebbe progettare una funzione di hash che genera hash unico per ogni stringhe di lunghezza da 0 a 6 caratteri (compreso) (sum(i=0..6) (26^i) = 3.10^8).