Perché la cache hashCode () di String non è 0?

Ho notato nel codice sorgente Java 6 per String che hashCode memorizza solo valori diversi da 0. La differenza di prestazioni è esibita dal seguente snippet:

public class Main{ static void test(String s) { long start = System.currentTimeMillis(); for (int i = 0; i < 10000000; i++) { s.hashCode(); } System.out.format("Took %d ms.%n", System.currentTimeMillis() - start); } public static void main(String[] args) { String z = "Allocator redistricts; strict allocator redistricts strictly."; test(z); test(z.toUpperCase()); } } 

L’esecuzione di questo in ideone.com fornisce il seguente risultato:

 Took 1470 ms. Took 58 ms. 

Quindi le mie domande sono:

  • Perché la cache hashCode () di String non è 0?
  • Qual è la probabilità che una stringa Java esegua l’hash su 0?
  • Qual è il modo migliore per evitare la penalizzazione delle prestazioni di ricalcolo del valore di hash ogni volta per stringhe che hash a 0?
  • È questo il modo migliore di memorizzare i valori nella cache? (Cache tutti tranne uno?)

Per il tuo divertimento, ogni riga qui è una stringa che hash a 0:

 pollinating sandboxes amusement & hemophilias schoolworks = perversive electrolysissweeteners.net constitutionalunstableness.net grinnerslaphappier.org BLEACHINGFEMININELY.NET WWW.BUMRACEGOERS.ORG WWW.RACCOONPRUDENTIALS.NET Microcomputers: the unredeemed lollipop... Incentively, my dear, I don't tessellate a derangement. A person who never yodelled an apology, never preened vocalizing transsexuals. 

Ti stai preoccupando di nulla. Ecco un modo per pensare a questo problema.

Supponiamo che tu abbia un’applicazione che non fa altro che sedersi attorno all’hashing Strings per tutto l’anno. Diciamo che ci vogliono mille stringhe, tutte in memoria, chiamate hashCode () su di loro ripetutamente in modalità round-robin, un milione di volte, poi ottengono altre migliaia di nuove stringhe e lo fanno di nuovo.

E supponiamo che la probabilità che il codice hash di una stringa sia zero era, in effetti, molto maggiore di 1/2 ^ 32. Sono sicuro che è un po ‘ più grande di 1/2 ^ 32, ma diciamo che è molto peggio di così, come 1/2 ^ 16 (la radice quadrata! Ora è molto peggio!).

In questa situazione, è necessario trarre maggiore vantaggio dagli ingegneri Oracle che migliorano il modo in cui i codici hash di queste stringhe vengono memorizzati nella cache rispetto a chiunque altro. Quindi scrivi a loro e chiedi loro di aggiustarlo. E lavorano la loro magia in modo che ogni volta che s.hashCode () è zero, ritorna istantaneamente (anche la prima volta! Un miglioramento del 100%!). E diciamo che lo fanno senza degradare le prestazioni per nessun altro caso.

Evviva! Ora la tua app è … vediamo … lo 0,0015% più veloce!

Ciò che prima richiedeva un’intera giornata ora richiede solo 23 ore, 57 minuti e 48 secondi!

E ricorda, abbiamo impostato lo scenario per dare ogni ansible beneficio del dubbio, spesso in modo ridicolo.

Ti sembra che ne valga la pena?

EDIT: dopo aver postato questo un paio di ore fa, ho lasciato correre uno dei miei processori alla ricerca di frasi di due parole con zero codici hash. Fin qui è venuto fuori: bequirtle zorillo, cronogrammic schtoff, chiostro contusivo, scricchiolanti organzine, boulderhead boulderhead, elettroanalitico esercitabile e favolosamente non dimostrabile. Si tratta di circa 2 ^ 35 possibilità, quindi con una distribuzione perfetta ci aspetteremmo di vedere solo 8. Ovviamente, quando sarà finita, avremo un po ‘di volte molte, ma non stranamente di più. La cosa più significativa è che ora ho trovato alcuni nomi di band / album interessanti! Nessun furto equo!

Usa 0 per indicare “Non ho ancora elaborato l’hashcode”. L’alternativa sarebbe utilizzare un flag booleano separato, che richiederebbe più memoria. (O per non memorizzare affatto l’hashcode, ovviamente).

Non mi aspetto un hash di molte stringhe a 0; probabilmente sarebbe logico che la routine di hashing evitasse deliberatamente 0 (ad esempio, traducesse un hash da 0 a 1 e lo memorizzasse nella cache). Ciò aumenterebbe le collisioni ma eviterebbe il rehashing. È troppo tardi per farlo adesso, dato che l’algoritmo String hashCode è esplicitamente documentato.

Per quanto riguarda se questa è una buona idea in generale: è un meccanismo di caching sicuramente efficiente, e potrebbe (vedi edit) essere ancora meglio con una modifica per evitare i valori di rehashing che finiscono con un hash di 0. Personalmente sarei interessato a vedere i dati che hanno portato Sun a ritenere che valesse la pena farlo in un primo momento – occupano 4 byte in più per ogni stringa mai creata, tuttavia spesso o raramente è sottoposta a hash, e l’unico vantaggio è per le stringhe che vengono sottoposte a hash più di una volta .

EDIT: Come KevinB fa notare in un commento altrove, il suggerimento “evita 0” sopra potrebbe avere un costo netto perché aiuta un caso molto raro , ma richiede un confronto extra per ogni calcolo di hash.

Penso che ci sia qualcosa di importante che mancano le altre risposte finora: il valore zero esiste in modo che il meccanismo di cache di hashCode funzioni in modo affidabile in un ambiente multi-thread.

Se avessi due variabili, come cacheHashCode e un valore booleano isHashCodeCalculated per indicare se cachedHashCode fosse stato calcolato, avresti bisogno della sincronizzazione dei thread perché le cose funzionassero in un ambiente con multithreading. E la sincronizzazione sarebbe dannosa per le prestazioni, soprattutto perché le stringhe vengono riutilizzate molto comunemente in più thread.

La mia comprensione del modello di memoria Java è un po ‘approssimativa, ma qui è più o meno quello che sta succedendo:

  1. Quando più thread accedono a una variabile (come il hashCode memorizzato nella cache), non c’è alcuna garanzia che ogni thread vedrà il valore più recente. Se una variabile inizia a zero, allora A lo aggiorna (lo imposta su un valore diverso da zero), quindi il thread B lo legge poco dopo, il thread B potrebbe ancora vedere il valore zero.

  2. C’è un altro problema con l’accesso ai valori condivisi da più thread (senza sincronizzazione): si può finire per provare a usare un object che è stato parzialmente inizializzato (la costruzione di un object non è un processo atomico). Anche le letture e le scritture multi-threaded di primitive a 64 bit come long e double non sono necessariamente atomiche, quindi se due thread cercano di leggere e modificare il valore di un long o di un double, un thread può finire per vedere qualcosa di strano e parzialmente impostato . O qualcosa del genere comunque. Ci sono problemi simili se si tenta di utilizzare due variabili insieme, come cachedHashCode e isHashCodeCalculated – un thread può facilmente arrivare e vedere l’ultima versione di una di queste variabili, ma una versione precedente di un’altra.

  3. Il solito modo per aggirare questi problemi multi-threading è utilizzare la sincronizzazione. Ad esempio, è ansible inserire tutti gli accessi al hashCode memorizzato nella cache all’interno di un blocco sincronizzato, oppure è ansible utilizzare la parola chiave volatile (anche se si deve prestare attenzione perché la semantica è un po ‘confusa).

  4. Tuttavia, la sincronizzazione rallenta. Ctriggers idea per qualcosa come una stringa hashCode. Le stringhe sono molto spesso utilizzate come chiavi in ​​HashMaps, quindi è necessario che il metodo hashCode funzioni bene, anche in ambienti multi-thread.

  5. Le primitive Java che sono a 32 bit o meno, come int, sono speciali. A differenza, ad esempio, di un valore lungo (valore a 64 bit), si può essere sicuri che non si leggerà mai un valore parzialmente inizializzato di un int (32 bit). Quando leggi un int senza sincronizzazione, non puoi essere sicuro di ottenere l’ultimo valore impostato, ma puoi essere sicuro che il valore che ottieni è un valore che è stato esplicitamente impostato ad un certo punto dalla tua discussione o un altro thread.

Il meccanismo di caching hashCode in java.lang.String è impostato per fare affidamento sul punto 5 sopra. Potresti capirlo meglio osservando la fonte di java.lang.String.hashCode (). Fondamentalmente, con più thread che chiamano hashCode in una volta, hashCode potrebbe essere calcolato più volte (o se il valore calcolato è zero o se più thread chiamano hashCode in una volta e entrambi vedono un valore memorizzato nella cache), ma si può essere sicuri che hashCode () restituirà sempre lo stesso valore. Quindi è robusto, ed è anche performante (perché non c’è sincronizzazione per fungere da collo di bottiglia negli ambienti multi-thread).

Come ho detto, la mia comprensione del modello di memoria Java è un po ‘approssimativa, ma sono abbastanza sicuro di aver capito l’essenza di quanto sopra. In fin dei conti è un idioma molto intelligente per memorizzare nella cache l’hashCode senza il sovraccarico della sincronizzazione.

0 non viene memorizzato nella cache poiché l’implementazione interpreta un valore memorizzato nella cache di 0 come “valore memorizzato nella cache non ancora inizializzato”. L’alternativa sarebbe stata utilizzare un java.lang.Integer , in cui null implicava che il valore non fosse ancora memorizzato nella cache. Tuttavia, ciò avrebbe significato un sovraccarico di storage aggiuntivo.

Per quanto riguarda la probabilità che il codice hash di una stringa venga calcolato come 0, direi che la probabilità è piuttosto bassa e può verificarsi nei seguenti casi:

  • La stringa è vuota (anche se ricalcolare ogni volta questo codice hash è O (1)).
  • Si verifica un overflow in cui il codice hash finale calcolato è 0 ( eg Integer.MAX_VALUE + h(c1) + h(c2) + ... h(cn) == 0 ).
  • La stringa contiene solo il carattere Unicode 0. Molto improbabile in quanto si tratta di un personaggio di controllo senza alcun significato a parte nel “mondo del nastro di carta” (!):

Da Wikipedia :

Il codice 0 (nome codice ASCII NUL) è un caso speciale. Nel nastro di carta, è il caso quando non ci sono buchi. È conveniente trattarlo come un carattere di riempimento senza indicare altrimenti .

Questa risulta essere una buona domanda, correlata a una vulnerabilità di sicurezza .

“Quando si esegue il hashing di una stringa, Java memorizza nella cache anche il valore hash nell’attributo hash, ma solo se il risultato è diverso da zero. Pertanto, il valore zero objective è particolarmente interessante per un utente malintenzionato in quanto impedisce la memorizzazione nella cache e le forze re-hashing.”

  • Perché la cache hashCode () di String non è 0?

Il valore zero è riservato nel senso che “il codice hash non è memorizzato nella cache”.

  • Qual è la probabilità che una stringa Java esegua l’hash su 0?

Secondo Javadoc, la formula per l’hashcode di una stringa è:

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

usando l’aritmetica int , dove s[i] è il carattere ith della stringa e n è la lunghezza della stringa. (L’hash della stringa vuota è definito come zero come caso speciale).

La mia intuizione è che la funzione hashcode come sopra fornisce una diffusione uniforms dei valori di hash String nell’intervallo di valori int . Una diffusione uniforms che significherebbe che la probabilità di un hashing di stringa generato a caso a zero era 1 in 2 ^ 32.

  • Qual è il modo migliore per evitare la penalizzazione delle prestazioni di ricalcolo del valore di hash ogni volta per stringhe che hash a 0?

La migliore strategia è ignorare il problema. Se esegui ripetutamente l’hashing dello stesso valore di stringa, c’è qualcosa di piuttosto strano nel tuo algoritmo.

  • È questo il modo migliore di memorizzare i valori nella cache? (Cache tutti tranne uno?)

Questo è uno scambio tra spazio e tempo. AFAIK, le alternative sono:

  • Aggiungi un flag cached a ogni object String, facendo in modo che ogni stringa Java assuma una parola in più.

  • Utilizzare il bit superiore del membro hash come flag memorizzato nella cache. In questo modo puoi memorizzare nella cache tutti i valori hash, ma hai solo la metà dei possibili valori hash stringa.

  • Non memorizzare codici hash sulle stringhe.

Penso che i designer Java abbiano fatto la scelta giusta per le stringhe, e sono sicuro che hanno fatto una profilazione approfondita che conferma la validità della loro decisione. Tuttavia, non segue che questo sarebbe sempre il modo migliore per gestire il caching.

(Si noti che ci sono due valori di stringa “comune” che vanno da zero a zero, la stringa vuota e la stringa costituita da un solo carattere NUL. Tuttavia, il costo del calcolo degli hash per questi valori è piccolo rispetto al costo del calcolo del hashcode per un valore String tipico).

Bene gente, mantiene 0 perché se è di lunghezza zero, finirà comunque come zero.

E non ci vuole molto per capire che la len è zero e quindi deve essere il codice hash.

Quindi, per il tuo codice-reviewz! Qui è tutto in gloria di Java 8:

  public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; } 

Come puoi vedere, questo restituirà sempre uno zero veloce se la stringa è vuota:

  if (h == 0 && value.length > 0) ... 

Il suggerimento “evitare 0” sembra appropriato da raccomandare come best practice in quanto aiuta un vero problema (degradazione delle prestazioni seriamente inaspettata in casi costruibili che possono essere forniti da un hacker) per il magro costo di un’operazione di filiale prima di una scrittura. C’è un po ‘di “degrado inatteso delle prestazioni” che può essere esercitato se le uniche cose che vanno in un hash impostato al valore adattato speciale. Ma questo è nel peggiore dei casi un doppio degrado piuttosto che illimitato.

Ovviamente, l’implementazione di String non può essere modificata, ma non è necessario perpetuare il problema.