Implémentation de hashmap Java 8 utilisant TreeNode au lieu de linkedlist
Selon ce post:
Http://coding-geek.com/how-does-a-hashmap-work-in-java/
Les hashmaps Java 8 utilisent un treenode au lieu d'une linkedlist (comme dans java 7) comme éléments du tableau.
TreeNodes ont la propriété spéciale d'agir en tant que linkedlist si le nombre d'éléments est petit, et d'agir en tant qu'arbre noir rouge s'il y a un grand nombre d'éléments. (Puisque les opérations impliquant un arbre noir rouge sont log (n)).
Cependant, cela ne nécessite-t-il pas la clé pour être comparable ou un certain ordre des clés pour exister?
Est-ce appliqué dans le hashmap java 8? Utilisera-t-il uniquement des arbres noirs rouges si les clés sont comparables (l'ordre des clés existe)?
1 answers
Utilisera-t-il uniquement des arbres noirs rouges si les clés sont comparables (ordre des touches existent)?
Non, quand HashMap est petit toutes les collisions sont résolues comme LinkedList. Regardez la source:
/**
* 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() la méthode convertira toutes les collisions en treemap lorsque le seuil est atteint.
Cependant, cela ne nécessite - t-il pas que la clé soit comparable ou commande des clés pour exister?
Vous pouvez mettre toutes les clés à hashmap. Selon l' java doc, null est une clé valide, et depuis null n'est pas Comparable, clés n'ont pas à être Comparable. Si une clé n'est pas Comparable, elle sera put en tant que LinkedList (via la table interne si le tableau est déjà converti en arbre).