Quando è solitamente utilizzato il metodo putTreeVal() in HashMap?Metodo putTreeVal() in HashMap JDK8
Quando si fa questo caso, dopo aver invocato put(K key, V value):
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
di solito si svolgono?
Il modo usuale di una mappa di hash è di avere un numero di contenitori (o secchi), in cui si seleziona il cestino per la nuova chiave in base al suo codice hash.
Il problema è che più chiavi possono arrivare allo stesso contenitore, in quanto vi è un numero limitato di contenitori. Il cestino è una lista. Quindi puoi arrivare al cestino in O (1) volta, ma poi devi cercare linearmente nella lista. Se l'elenco diventa lungo, peggiora le prestazioni della tabella hash.
Quindi l'attuale implementazione di HashMap migliora questo problema modificando la struttura del cestino se il contenitore diventa troppo lungo. Se il contenitore contiene già più di 8 voci e il numero di contenitori è superiore a 64, il contenitore viene convertito da un elenco a un albero rosso-nero. Un albero rosso-nero è un albero di ricerca equilibrato. Ciò significa che la ricerca sarà O (log n), che è preferibile a O (n).
Così ora, quando si inserisce un valore in un raccoglitore, è necessario controllare quale contenitore è. Se si tratta di un elenco semplice, aggiungere all'elenco e, se si tratta di un albero, aggiungere all'albero e bilanciarlo.
Grazie a @RealSkeptic, molto bello. Ho provato a sopraffare uno dei bucket, lo ho debugato e poi ho chiarito che è troppo difficile scrivere una tale coppia di hashCode() ed equils() che gli elementi entrano nello stesso bucket per lanciare treeifyBin() –
Stai chiedendo di implementazione? L'archiviazione per più voci nello stesso bucket hash è stata aggiornata da un elenco collegato singolarmente a un albero binario. Quindi questo è usato per aggiungere una voce all'albero in un secchio hash se c'è uno scontro. –
si noti che si tratta di un dettaglio di implementazione e quindi soggetto a modifiche nelle versioni future. – the8472