Perché le mappe di hash in Java 8 utilizzano un albero binario invece di un elenco collegato?

Question

Recentemente sono venuto a sapere che in Java 8 le mappe hash utilizzano un albero binario invece di una lista collegata e il codice hash viene utilizzato come fattore di ramificazione. Comprendo che in caso di collisione elevata la ricerca è ridotta a O (log n) da O (n) usando alberi binari. La mia domanda è: cosa fa veramente bene quando la complessità temporale ammortizzata è ancora O (1) e forse se si forza a memorizzare tutte le voci nello stesso bucket fornendo lo stesso codice hash per tutti le chiavi possiamo vedere una significativa differenza di tempo ma nessuno nelle loro menti lo farebbe.

L'albero binario utilizza anche più spazio dell'elenco collegato singolarmente poiché memorizza entrambi i nodi sinistro e destro. Perché aumentare la complessità dello spazio quando non c'è assolutamente alcun miglioramento nella complessità del tempo, ad eccezione di alcuni casi di test spuri.

Answer 1

Si tratta principalmente di modifiche relative alla sicurezza. Mentre in situazioni normali è raramente possibile avere molte collisioni, se le chiavi di hash arrivano da fonti non attendibili (ad es. I nomi delle intestazioni HTTP ricevute dal client), allora è possibile e non molto difficile creare appositamente l'input, quindi i tasti risultanti avranno il stesso codice hash. Ora, se esegui molte ricerche, potresti riscontrare un rifiuto di servizio. Sembra che ci sia un sacco di codice in the wild che è vulnerabile a questo tipo di attacchi, quindi è stato deciso di risolvere questo problema sul lato Java.

Per ulteriori informazioni, fare riferimento a JEP-180.

Answer 2

La tua domanda contiene alcune premesse sbagliate.

1. Una collisione secchio non è necessariamente una collisione hash. Non è necessario che lo stesso codice hash per due oggetti finisca nello stesso bucket. Il bucket è un elemento di una matrice e il codice hash deve essere mappato su un particolare indice. Poiché la dimensione dell'array deve essere ragionevole rispetto alla dimensione dello Map, non è possibile aumentare arbitrariamente la dimensione dell'array per evitare collisioni con secchi. C'è anche la limitazione teorica che una dimensione dell'array può essere al massimo 2³¹ mentre ci sono 2 ² possibili codici hash.
2. Avere una collisione hash non è un segno di programmazione errata. Per tutti gli oggetti che hanno uno spazio di valore maggiore di 2 ², la possibilità di oggetti distinti con lo stesso codice hash è inevitabile. String s sono un esempio ovvio, ma anche un Point con due valori o una chiave semplice Long hanno collisioni hash inevitabili. Quindi potrebbero essere più comuni di quanto si pensi e dipende in larga misura dal caso d'uso.
3. L'implementazione passa a un albero binario solo quando il numero di collisioni in un bucket supera una determinata soglia, quindi i costi di memoria più elevati si applicano solo quando ripagano. sembra esserci un malinteso comune su come funzionano. Poiché la collisione con benna non è necessariamente collisione di hash, la ricerca binaria cercherà prima i codici hash. Solo quando i codici hash sono identici e la chiave implementa appropriatamente Comparable, verrà utilizzato il suo ordine naturale. Gli esempi che potresti aver trovato sul Web utilizzano deliberatamente lo stesso codice hash per gli oggetti per dimostrare l'uso dell'implementazione Comparable che altrimenti non verrebbe visualizzata. Ciò che attivano è solo l'ultima risorsa dell'attuazione.
4. Come Tagir pointed out, questo problema potrebbe influire sulla sicurezza di un software poiché un fallback lento può aprire la possibilità di attacchi DoS. Ci sono stati diversi tentativi nelle versioni precedenti di JRE per risolvere questo problema che ha avuto più svantaggi del consumo di memoria di un albero binario. Ad esempio, c'è stato un tentativo di randomizzare la mappatura dei codici hash alle voci dell'array in Java 7 che ha causato un sovraccarico di inizializzazione come documentato in this bug report. Questo non è il caso di questa nuova implementazione.