Le framework Collections de Java : listes, sets, maps et files

Tout programme Java qui manipule plus d'une chose à la fois utilise java.util. Le framework est assez petit pour être maîtrisé entièrement — une poignée d'interfaces et une douzaine d'implémentations dont vous vous servirez vraiment — mais assez riche pour qu'une LinkedList à la place d'une ArrayList, ou une HashMap là où il fallait une TreeMap, coûte discrètement en performances ou en justesse. Ce guide présente la hiérarchie, le modèle de coûts, les règles du hachage et de l'ordre, ainsi que les opérations vers lesquelles se tournent les développeurs expérimentés. Le code cible Java 21.

La hiérarchie des interfaces

Le framework sépare ce que promet une collection (les interfaces) de la manière dont elle stocke les données (les implémentations). Programmez contre l'interface et choisissez l'implémentation au moment de la construction.

Iterable
└── Collection
    ├── List          ordered, indexed, duplicates allowed
    ├── Set           no duplicates
    │   └── SortedSet → NavigableSet   sorted by natural order or Comparator
    └── Queue         head-first access
        └── Deque     both ends

Map (not a Collection)   key → value, unique keys
└── SortedMap → NavigableMap

Map est volontairement en dehors de Collection : une map est un ensemble d'associations, pas un sac d'éléments, et ses méthodes keySet(), values() et entrySet() sont les vues qui permettent de la traiter comme une collection.

Java 21 a ajouté les collections séquencées (JEP 431) : SequencedCollection, SequencedSet et SequencedMap dotent List, Deque, LinkedHashSet, LinkedHashMap et les types triés de méthodes uniformes getFirst(), getLast(), addFirst(), removeLast() et reversed(). Avant Java 21, il fallait écrire list.get(list.size() - 1) ou parcourir un ListIterator à reculons.

Les listes

Une List est une séquence ordonnée avec accès par position. Deux implémentations comptent.

ArrayList stocke ses éléments dans un tableau qui s'agrandit (de moitié environ) lorsqu'il est plein. L'accès par index se fait en temps constant, l'ajout en fin en temps constant amorti, et l'insertion ou la suppression au milieu coûte un décalage mémoire de la fin du tableau — rapide en pratique, car System.arraycopy est une boucle native très serrée. L'itération tire bien parti du cache. C'est la liste par défaut.

LinkedList est une liste doublement chaînée de nœuds. L'accès par position part d'une extrémité, donc get(i) est linéaire ; chaque nœud est un objet à part avec deux pointeurs, si bien que la mémoire occupée est trois à quatre fois celle d'une ArrayList pour de petits éléments, et l'itération saute un peu partout dans le tas. Elle ne gagne que pour une suppression à un curseur déjà positionné par un ListIterator. Elle implémente aussi Deque, mais ArrayDeque fait ce travail mieux qu'elle.

List<String> hosts = new ArrayList<>(List.of("db1", "db2", "cache"));
hosts.add("queue");
hosts.set(0, "db-primary");
hosts.remove("cache");               // remove by value (first match)
hosts.remove(0);                      // remove by index — beware with List<Integer>
String last = hosts.getLast();        // Java 21
hosts.sort(Comparator.naturalOrder());

Le piège de la surcharge de remove est bien réel : List<Integer> possède à la fois remove(int index) et remove(Object o), et list.remove(3) choisit la version par index. Écrivez list.remove(Integer.valueOf(3)) pour supprimer par valeur.

Les sets et le contrat de hachage

Un Set refuse les doublons, un « doublon » étant un élément pour lequel equals renvoie true. La façon de les détecter dépend de l'implémentation.

HashSet range ses éléments dans une table de hachage. add, contains et remove s'exécutent en temps constant en moyenne ; l'ordre d'itération n'est pas spécifié et peut changer quand le set se redimensionne. Il repose sur le contrat hérité d'Object : des éléments égaux au sens d'equals doivent avoir le même hashCode. Rompez ce contrat (en redéfinissant l'une des méthodes sans l'autre) et le set stocke des « doublons » ou ne retrouve plus des éléments qu'il contient. Depuis Java 8, un bucket qui accumule beaucoup de clés en collision se transforme en arbre équilibré plutôt qu'en liste chaînée, ce qui limite les dégâts d'une fonction de hachage pathologique, mais un bon hashCode reste important.

LinkedHashSet est un HashSet qui maintient en plus une liste chaînée de l'ordre d'insertion. Même coût, itération prévisible, un peu plus de mémoire. Utilisez-le dès que des tests, des logs ou des utilisateurs verront l'ordre.

TreeSet garde ses éléments triés dans un arbre rouge-noir, selon leur ordre naturel (Comparable) ou un Comparator que vous fournissez. Les opérations sont logarithmiques et vous gagnez des requêtes par intervalle : headSet, tailSet, subSet, ceiling, floor. Un TreeSet décide de l'égalité avec compareTo ou compare, pas avec equals : un comparateur qui renvoie 0 pour deux éléments distincts en fera disparaître un.

EnumSet est un vecteur de bits spécialisé pour les éléments d'une enum : minuscule, extrêmement rapide, et le bon choix dès que le type des éléments est une enum.

record Tag(String name) implements Comparable<Tag> {
    @Override public int compareTo(Tag o) { return name.compareToIgnoreCase(o.name); }
}

Set<Tag> tags = new TreeSet<>();
tags.add(new Tag("Java"));
tags.add(new Tag("java"));           // compareTo says equal → not added
System.out.println(tags.size());     // 1, even though the records are not equals()

Les maps

Une Map associe des clés uniques à des valeurs. On y retrouve les trois mêmes stratégies de stockage.

L'interface Map a gagné en Java 8 une série de méthodes qui remplacent la vieille routine « vérifier, puis put » :

Map<String, List<String>> byDept = new HashMap<>();

// Before Java 8
List<String> names = byDept.get("eng");
if (names == null) { names = new ArrayList<>(); byDept.put("eng", names); }
names.add("Ada");

// Now
byDept.computeIfAbsent("eng", k -> new ArrayList<>()).add("Ada");

Map<String, Integer> counts = new HashMap<>();
counts.merge("java", 1, Integer::sum);            // increment or initialise
int hits = counts.getOrDefault("kotlin", 0);
counts.putIfAbsent("scala", 0);
counts.replaceAll((k, v) -> v * 2);

computeIfAbsent, merge et getOrDefault sont les trois à retenir. Parcourez une map via entrySet() quand vous avez besoin des deux moitiés ; parcourir keySet() puis appeler get pour chaque clé fait deux recherches par entrée.

LinkedHashMap accepte dans son constructeur un indicateur d'ordre d'accès et offre un point d'extension removeEldestEntry ; ensemble, ils permettent d'écrire un cache LRU borné en une dizaine de lignes — un grand classique des entretiens, et un outil parfois utile en production.

Les clés doivent être stables. Une clé dont le hashCode change après l'insertion (un objet mutable dont le hash dépend de ses champs) est perdue : la map la cherche dans le bucket correspondant au nouveau hash et ne la trouve jamais. Utilisez des clés immuables — chaînes, nombres, enums, records.

Files, deques et piles

Queue offre un accès par la tête avec deux familles de méthodes : add/remove/element lèvent une exception lorsqu'elles ne peuvent pas aboutir, tandis que offer/poll/peek renvoient false ou null. Deque étend ce modèle aux deux extrémités.

ArrayDeque repose sur un tableau circulaire redimensionnable ; c'est la bonne implémentation aussi bien pour une file FIFO que pour une pile LIFO. Elle est plus rapide que LinkedList dans les deux cas, et plus rapide que l'ancienne classe Stack, synchronisée et dérivée de Vector — n'utilisez pas Stack dans du code neuf.

PriorityQueue est un tas binaire qui renvoie toujours le plus petit élément selon l'ordre naturel ou le comparateur. L'insertion et le retrait sont logarithmiques ; le parcours ne rend pas les éléments triés, seul poll() le fait.

Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
System.out.println(stack.pop());   // second

Queue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
pq.addAll(List.of(3, 9, 1));
System.out.println(pq.poll());     // 9

Les variantes bloquantes — ArrayBlockingQueue, LinkedBlockingQueue — ajoutent put et take, qui attendent, et relèvent de la boîte à outils de la concurrence.

Itération, ordre et modification

La boucle for-each se compile en Iterator : hasNext(), next(), et on recommence. La plupart des collections non concurrentes sont fail-fast : si la collection subit une modification structurelle pendant l'itération par autre chose que le remove de l'itérateur lui-même, le next() suivant lève une ConcurrentModificationException. C'est une détection opportuniste d'un bug, pas une garantie de thread-safety.

List<Order> orders = ...;

// Wrong: throws ConcurrentModificationException
for (Order o : orders) if (o.isCancelled()) orders.remove(o);

// Right, and shortest
orders.removeIf(Order::isCancelled);

// Also right, when you need the iterator anyway
for (Iterator<Order> it = orders.iterator(); it.hasNext(); ) {
    if (it.next().isCancelled()) it.remove();
}

Le tri se fait soit sur place — list.sort(comparator) ou Collections.sort(list) —, soit dans une nouvelle collection avec un stream. Comparator se compose bien : Comparator.comparing(Person::lastName).thenComparing(Person::firstName).reversed(), avec nullsFirst/nullsLast pour les champs facultatifs. Le tri est un tri fusion stable (TimSort) : les éléments égaux conservent leur ordre relatif, ce qui compte quand on trie successivement sur plusieurs clés.

Collections immuables et vues

Java 9 a introduit des fabriques pratiques : List.of(...), Set.of(...), Map.of(k1, v1, ...), Map.ofEntries(...), puis Java 10 a ajouté List.copyOf, Set.copyOf et Map.copyOf. Elles renvoient des collections non modifiables : tout mutateur lève UnsupportedOperationException, les éléments null sont refusés, et Set.of/Map.of lèvent une exception en cas de clé en double. Leur ordre d'itération est volontairement rendu aléatoire à chaque exécution de la JVM, pour que personne n'en dépende par accident.

Trois notions se ressemblent mais doivent être distinguées :

• Collection immuable (List.of) : elle ne peut jamais changer.
• Vue non modifiable (Collections.unmodifiableList(inner)) : impossible de la modifier à travers la vue, mais si l'original change, la vue le reflète. Idéal pour exposer un état interne sans le copier.
• Copie défensive (new ArrayList<>(inner) ou List.copyOf(inner)) : un instantané qu'aucun des deux côtés ne peut affecter.

Les vues sont partout dans le framework : map.keySet(), list.subList(a, b) et Arrays.asList(array) sont toutes des fenêtres vivantes sur d'autres données. Supprimer dans keySet() supprime dans la map ; vider une subList retire cette plage de la liste. Puissant quand c'est voulu, déroutant quand ça ne l'est pas.

Collections propose aussi synchronizedList et consorts, qui entourent chaque méthode d'un verrou. Ils sécurisent les appels individuels, mais pas les séquences d'appels (vérifier puis agir) ni l'itération, et ont été largement supplantés par les collections de java.util.concurrent.

Choisir une implémentation

Indiquez une capacité initiale quand vous connaissez la taille : new ArrayList<>(10_000) ou HashMap.newHashMap(expected) (Java 19) évitent une série de redimensionnements. Pensez aussi à la collection que vous renvoyez : renvoyer List.of() ou Collections.emptyList() ne coûte rien, alors qu'allouer une ArrayList vide à chaque appel finit par peser.

Erreurs fréquentes

Clés de hachage mutables. Un Set<Point> où Point a des setters, ou une map dont la clé est une liste que vous complétez ensuite, perd des éléments sans bruit. Les clés doivent être immuables.

Compter sur l'ordre d'une HashMap. Il n'est pas spécifié et change avec les redimensionnements et les versions du JDK. Des tests qui passent par chance échouent après un refactoring.

Arrays.asList sur un tableau de primitifs. Arrays.asList(new int[]{1, 2}) donne une List<int[]> à un seul élément. Utilisez IntStream.of(...).boxed().toList() ou un Integer[].

Prendre subList pour une copie. C'est une vue : les modifications structurelles du parent l'invalident, et les modifications faites à travers elle altèrent le parent.

Utiliser LinkedList comme file ou Stack comme pile. ArrayDeque est plus rapide et plus légère dans les deux cas.

Null dans les collections modernes. List.of, Map.of et ConcurrentHashMap refusent null. Décidez dès le départ si null a un sens dans vos données ; en général non, et Optional ou une valeur sentinelle explicite est plus clair.

Parcourir keySet() puis appeler get. Deux recherches par entrée ; parcourez entrySet().

Un comparateur de TreeSet incohérent avec equals. Les éléments que le comparateur juge égaux sont dédoublonnés même si equals n'est pas d'accord. Rendez-les cohérents ou documentez la différence.

Points clés à retenir

• Déclarez vos variables par leur interface (List, Set, Map, Deque) et choisissez l'implémentation à la construction.
• ArrayList, HashSet, HashMap et ArrayDeque sont les choix par défaut ; passez à Linked* quand l'ordre d'itération compte et à Tree* quand il faut trier ou faire des requêtes par intervalle.
• Les collections à base de hachage dépendent d'une paire equals/hashCode cohérente et de clés qui ne changent jamais ; celles à base d'arbre ne dépendent que du comparateur.
• Pendant une itération, ne modifiez la collection que via removeIf ou l'itérateur ; tout le reste lève une ConcurrentModificationException.
• List.of et ses cousines sont immuables et hostiles à null ; Collections.unmodifiable* et subList sont des vues vivantes ; copyOf et les constructeurs de copie produisent des instantanés.
• Utilisez computeIfAbsent, merge et getOrDefault plutôt que « vérifier puis put », et entrySet() pour l'itération.