Java attuazione 8 hashmap utilizzando TreeNode anziché LinkedList

Question

Secondo questo post:

java 8 HashMaps utilizzare un TreeNode invece di una LinkedList (come in Java 7) come elementi della matrice.

I TreeNode hanno la proprietà speciale di agire come una lista collegata se il numero di elementi è piccolo e agisce come un albero nero rosso se c'è un numero elevato di elementi. (Poiché le operazioni che coinvolgono un albero nero rosso sono log (n)).

Tuttavia, ciò non richiede che la chiave sia comparabile o che esista un ordinamento delle chiavi?

Questo è applicato all'hashmap di java 8? Userà solo alberi neri rossi se le chiavi sono comparabili (l'ordine delle chiavi esiste)?

Answer 1

Userà solo alberi neri rossi se i tasti sono comparabili (l'ordine di chiavi esiste)?

No, quando è piccolo HashMap tutte le collisioni sono risolte come LinkedList. Guardate la fonte:

metodo

/** 
* Replaces all linked nodes in bin at index for given hash unless 
* table is too small, in which case resizes instead. 
*/ 

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st, TREEIFY_THRESHOLD = 8 
    treeifyBin(tab, hash); 
    break; 

treeifyBin() convertirà tutte le collisioni di treemap quando viene raggiunta la soglia.

Tuttavia, ciò non richiede che la chiave sia comparabile o qualche ordinamento delle chiavi?

È possibile inserire qualsiasi chiave in hashmap. Secondo lo java doc, null è una chiave valida e poiché null non è Comparable, le chiavi non devono essere Comparable. Se una chiave non è Comparable sarà put come LinkedList (attraverso la tabella interna se l'array è già stato convertito come albero).