0Pricing
Java Academy · Leçon

Transformation en arbre et performances

Gestion des collisions depuis Java 8

Transformation en arbre et performances est une leçon Java Academy gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Java Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Java Academy comprend 4 leçons au total.

Le problème des collisions

Avant Java 8, un compartiment avec de nombreuses collisions devenait une longue liste chaînée. La recherche dans ce compartiment se dégradait en O(n).

Un attaquant pouvait exploiter ce comportement avec des clés conçues à cet effet pour provoquer un déni de service, toutes étant hachées vers un seul compartiment.

public class Main {
    public static void main(String[] args) {
        // All these strings can be made to collide in one bucket
        System.out.println("FB".hashCode() == "Ea".hashCode());
    }
}

La transformation en arbre de Java 8

Java 8 a ajouté la transformation en arbre. Lorsqu’un seul compartiment contient trop d’entrées, la liste chaînée est convertie en un arbre rouge-noir équilibré.

La recherche dans ce compartiment passe alors à O(log n) au lieu de O(n).

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i < 1000; i++) m.put(i, i);
        System.out.println("Lookups stay fast: " + m.get(742));
    }
}

Le seuil : TREEIFY_THRESHOLD

La constante TREEIFY_THRESHOLD vaut 8. Un compartiment est converti en arbre lorsqu’il atteint 8 entrées.

Mais une deuxième condition s’applique : la table doit également avoir une taille d’au moins MIN_TREEIFY_CAPACITY (64) ; sinon, la map est redimensionnée.

public class Main {
    public static void main(String[] args) {
        int TREEIFY_THRESHOLD = 8;
        int MIN_TREEIFY_CAPACITY = 64;
        System.out.println("Treeify when bucket size >= " + TREEIFY_THRESHOLD);
        System.out.println("...and table capacity >= " + MIN_TREEIFY_CAPACITY);
    }
}

Redimensionner d’abord, convertir en arbre ensuite

Si un compartiment déborde alors que la table est encore petite (moins de 64 éléments), HashMap redimensionne d’abord la table.

Le redimensionnement redistribue généralement les entrées et élimine le point chaud ; la transformation en arbre n’est donc qu’une solution de dernier recours pour les répartitions de hash réellement mauvaises.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16);
        for (int i = 0; i < 50; i++) m.put(i, i);
        // Many resizes happened before any treeify would
        System.out.println("size = " + m.size());
    }
}

Conversion inverse en liste

Les arbres ne sont pas permanents. Si des suppressions réduisent un compartiment sous UNTREEIFY_THRESHOLD (6), l’arbre redevient une liste chaînée.

L’écart entre 8 (conversion en arbre) et 6 (conversion inverse) évite les allers-retours incessants autour de la limite.

public class Main {
    public static void main(String[] args) {
        System.out.println("TREEIFY_THRESHOLD   = 8");
        System.out.println("UNTREEIFY_THRESHOLD = 6");
        System.out.println("Gap prevents flip-flopping at the edge");
    }
}

Les arbres nécessitent un ordre comparable ou d’identité

Un arbre rouge-noir doit ordonner ses entrées. HashMap compare d’abord les codes de hachage ; en cas d’égalité, les ex æquo sont départagés par Comparable si les clés l’implémentent, sinon par un départage stable fondé sur les noms de classes et l’identité.

Les clés Comparable (comme String ou un entier) fournissent l’ordre d’arbre le plus clair.

public class Main {
    public static void main(String[] args) {
        System.out.println("String is Comparable: " + ("a" instanceof Comparable));
        System.out.println("Integer is Comparable: " + (Integer.valueOf(1) instanceof Comparable));
    }
}

Conséquences pratiques

Dans la plupart des programmes réels utilisant de bons codes de hachage, vous ne verrez jamais de transformation en arbre. Les compartiments restent courts.

La transformation en arbre est un filet de sécurité qui limite la recherche dans le pire cas à O(log n), même lorsque le hachage est mauvais ou soumis à une attaque.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("alpha", 1);
        m.put("beta", 2);
        m.put("gamma", 3);
        // Tiny buckets, plain linked lists, no trees needed
        System.out.println(m.get("beta"));
    }
}

Un hashCode constant force la création d’arbres

Si vous renvoyez délibérément un hashCode constant, chaque clé arrive dans un seul compartiment. Avec une capacité d’au moins 64, ce compartiment est converti en arbre.

Cela illustre le filet de sécurité, mais révèle une mauvaise conception. Corrigez plutôt le hashCode.

import java.util.HashMap;
import java.util.Map;

public class Main {
    static class Bad implements Comparable<Bad> {
        final int v;
        Bad(int v) { this.v = v; }
        @Override public int hashCode() { return 1; } // forces collisions
        @Override public boolean equals(Object o) { return o instanceof Bad b && b.v == v; }
        @Override public int compareTo(Bad o) { return Integer.compare(v, o.v); }
    }
    public static void main(String[] args) {
        Map<Bad, Integer> m = new HashMap<>();
        for (int i = 0; i < 100; i++) m.put(new Bad(i), i);
        System.out.println("All in one bucket, still works: " + m.get(new Bad(50)));
    }
}

Le coût mémoire des arbres

Les nœuds d’arbre sont plus volumineux que les nœuds de liste chaînée simples, car ils stockent des références vers le parent, les fils gauche et droit, ainsi que la couleur.

C’est une autre raison pour laquelle la transformation en arbre est une solution de secours et non le comportement par défaut : les arbres échangent de la mémoire contre de meilleures performances dans le pire cas.

public class Main {
    public static void main(String[] args) {
        System.out.println("Node: hash, key, value, next");
        System.out.println("TreeNode: + parent, left, right, prev, red flag");
        System.out.println("=> trees cost more memory per entry");
    }
}

Comment éviter la transformation en arbre

Vous ne devriez presque jamais compter sur la transformation en arbre. Évitez-la en :

  • Écrivant un hashCode() bien réparti.
  • Utilisant des types intégrés ou des enregistrements comme clés.
  • Dimensionnant initialement la map pour réduire les collisions.
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class Main {
    record Key(int a, int b) {}
    public static void main(String[] args) {
        Map<Key, Integer> m = new HashMap<>(256);
        for (int i = 0; i < 200; i++) m.put(new Key(i, i * 31), i);
        System.out.println("Even distribution, fast lookups: " + m.get(new Key(10, 310)));
    }
}

Résumé des performances

Coûts des opérations de HashMap :

  • Bon hash : O(1) en moyenne.
  • Compartiment chaîné : O(n) par compartiment dans le pire cas.
  • Compartiment converti en arbre : O(log n) par compartiment.

La transformation en arbre limite le pire cas, mais un bon hashCode vous maintient dans un monde en O(1).

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(1 << 14);
        for (int i = 0; i < 10000; i++) m.put(i, i);
        System.out.println("10k entries, O(1) get: " + m.get(9999));
    }
}

Vérification rapide

Testez vos connaissances sur la transformation en arbre.

Récapitulatif

Vous avez appris comment HashMap moderne gère les collisions :

  • Les compartiments sont convertis en arbres à partir de 8 entrées lorsque la capacité est d’au moins 64.
  • Les arbres fournissent une recherche dans le pire cas en O(log n).
  • Les compartiments redeviennent des listes sous 6 entrées.
  • Un bon hashCode signifie que vous déclenchez rarement ce filet de sécurité.

Vous avez terminé le cours sur le fonctionnement interne de HashMap.

public class Main {
    public static void main(String[] args) {
        System.out.println("Treeification course complete");
    }
}

Questions Fréquemment Posées

La leçon « Transformation en arbre et performances » est-elle gratuite ?

Oui — le texte complet de « Transformation en arbre et performances » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Java Academy, passe à CoddyKit PRO. Le cours Java Academy comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Transformation en arbre et performances » ?

Gestion des collisions depuis Java 8 Tu pratiques Java Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Java Academy ?

Aucune expérience préalable n'est requise. Java Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.

Combien de temps prend la leçon « Transformation en arbre et performances » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Java Academy ?

Oui. Chaque leçon Java Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Fonctionnement de HashMap
  2. Contrat equals/hashCode
  3. Implémenter hashCode
  4. Transformation en arbre et performances
← Retour à Java Academy