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
HashMapne peut offrir.- Méthodes de navigation
floorKey(≤),ceilingKey(≥),lowerKey(<),higherKey(>),firstKey,lastKey,headMap,tailMap,subMap. Le vrai intérêt deTreeMap.- LinkedHashMap
Une
HashMapqui conserve l'ordre d'insertion — ou, avecaccessOrder = true, l'ordre d'accès. Mêmes performances qu'uneHashMap.- removeEldestEntry
Méthode de
LinkedHashMapà redéfinir pour supprimer automatiquement la plus ancienne entrée. AvecaccessOrder = 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
TreeMaptrie selon l'ordre naturel des clés (Comparable) ou selon unComparatorfourni à la construction — utile pour un ordre décroissant ou métier.
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.