Quel type d'arbre utilisé dans java 8 HashMap bucket?

Question

Quel type d'arbre utilisé dans java 8 HashMap bucket?

Comme je le sais dans java8, l'implémentation du seau HashMap a été un peu modifiée. Si la taille du compartiment dépasse une certaine valeur, la liste se transforme en "arbre équilibré".

Je ne comprends pas
1. quel type d'arbre équilibré utilisé dans Oracle JDK? (AVL? rouge-noir? quelque chose comme dans les bases de données pour les index?)
2. Est-il d'arbres binaires?
3. Si je comprends bien, le tri s'exécute en fonction du hashcode. Par exemple dans mon seau j'ai 102 éléments. 100 valeurs avec hashcode également 12 (je comprends que cela vaut la peine mais j'ai juste besoin de comprendre ce comportement) et 2 avec hashcode 22.
Comment fonctionne la recherche sera exécutée pour la valeur ?

7

French java hashmap java-8

Author: Marat Safin, 2016-12-26

Source

1 answers

score 7 · Accepted Answer

En regardant l'implémentation, cela ressemble à un arbre binaire. Plus précisément, le commentaire ci-dessous suggère que c'est un arbre rouge-noir:

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    ...
}

Quant à la gestion des codes de hachage égaux, ceci est abordé dans le Javadoc:

Tree bins (c.-à-d., bins dont les éléments sont tous les TreeNodes) sont ordonné principalement par hashCode, mais dans le cas des liens, si deux les éléments sont les mêmes " class C implements Comparable<C>", tapez alors leur méthode compareTo est utilisée pour la commande.

Les TreeNodes utilisés dans HashMap sont dits structurés de manière similaire à ceux de TreeMap.

Vous pouvez voir l'implémentation de la recherche d'un TreeNode contenant la clé requise ici:

    /**
     * Finds the node starting at root p with the given hash and key.
     * The kc argument caches comparableClassFor(key) upon first use
     * comparing keys.
     */
    final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
        TreeNode<K,V> p = this;
        do {
            int ph, dir; K pk;
            TreeNode<K,V> pl = p.left, pr = p.right, q;
            if ((ph = p.hash) > h)
                p = pl;
            else if (ph < h)
                p = pr;
            else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                return p;
            else if (pl == null)
                p = pr;
            else if (pr == null)
                p = pl;
            else if ((kc != null ||
                      (kc = comparableClassFor(k)) != null) &&
                     (dir = compareComparables(kc, k, pk)) != 0)
                p = (dir < 0) ? pl : pr;
            else if ((q = pr.find(h, k, kc)) != null)
                return q;
            else
                p = pl;
        } while (p != null);
        return null;
    }

Comme vous pouvez le voir, ceci est similaire à la recherche d'arborescence de recherche binaire standard. Ils recherchent d'abord un TreeNode ayant le même hashCode que la clé recherchée (car un seul compartiment d'un HashMap peut contenir des entrées ayant des hashCodes différents). Ensuite, il continue jusqu'à ce qu'un TreeNode ayant une clé égale à la clé requise soit trouver. La recherche secondaire utilise compareTo si la classe de la clé implémente Comparable. Sinon, une recherche complète est effectuée.