Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › TreeMap et LinkedHashMap : quand l'ordre compte

TreeMap et LinkedHashMap : quand l'ordre compte

Maps, Sets et regroupementsintermediaire

Une HashMap ne sait rien de l'ordre de ses clés. Quand l'ordre compte, deux structures prennent le relais.

TreeMap — clés triées, navigation par proximité :

TreeMap<Integer, String> paliers = new TreeMap<>();
paliers.put(0, "bronze");
paliers.put(1000, "argent");
paliers.put(5000, "or");

paliers.floorEntry(3200).getValue();   // "argent" — le plus grand palier ≤ 3200
paliers.ceilingKey(3200);              // 5000     — le plus petit ≥ 3200
paliers.headMap(5000);                 // {0=bronze, 1000=argent}
paliers.firstKey();  paliers.lastKey();

Aucune HashMap ne peut répondre à ces questions sans parcourir toutes ses entrées.

LinkedHashMap — ordre d'insertion, ou d'accès :

Map<String, Integer> ordonnee = new LinkedHashMap<>();   // ordre d'insertion

// Cache LRU : dix lignes
Map<String, String> cache = new LinkedHashMap<>(16, 0.75f, true) {   // accessOrder = true
    @Override protected boolean removeEldestEntry(Map.Entry<String, String> plusAncienne) {
        return size() > 100;
    }
};

Le compromis : TreeMap coûte O(log n) au lieu de O(1). On le paie volontiers quand on a besoin de l'ordre ; jamais « au cas où ».

Les termes à connaître

TreeMap

Une Map dont les clés sont maintenues triées (arbre rouge-noir). Toutes les opérations en O(log n), avec des méthodes de navigation qu'aucune HashMap ne peut offrir.

Méthodes de navigation

floorKey (≤), ceilingKey (≥), lowerKey (<), higherKey (>), firstKey, lastKey, headMap, tailMap, subMap. Le vrai intérêt de TreeMap.

LinkedHashMap

Une HashMap qui conserve l'ordre d'insertion — ou, avec accessOrder = true, l'ordre d'accès. Mêmes performances qu'une HashMap.

removeEldestEntry

Méthode de LinkedHashMap à redéfinir pour supprimer automatiquement la plus ancienne entrée. Avec accessOrder = true, elle donne un cache LRU en dix lignes.

Cache LRU

Least Recently Used : quand le cache est plein, on évince l'élément dont l'accès est le plus ancien. L'exercice de structure de données le plus demandé en entretien.

Ordre naturel ou comparateur

Une TreeMap trie selon l'ordre naturel des clés (Comparable) ou selon un Comparator fourni à la construction — utile pour un ordre décroissant ou métier.

Lire l'explication détaillée et faire le quiz →

Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.