Java Collections Framework — Vue d'ensemble

Presque tout programme finit par manipuler un groupe de choses — des commandes en attente d'expédition, les mots d'un document, les utilisateurs connectés, la file de tâches en attente qu'un thread ouvrier traitera bientôt. La réponse de Java à la question « où stocker ce groupe ? » est le Collections Framework : un ensemble coordonné d'interfaces dans java.util, une douzaine d'implémentations qui les réalisent, et une classe utilitaire d'algorithmes (Collections) qui opère sur les interfaces plutôt que sur une implémentation concrète. Ce chapitre est la carte — ce qu'il y a dans le framework, pourquoi il est conçu ainsi, et quelle famille choisir dans quelle situation. Chaque chapitre de cette partie plonge en profondeur dans l'une des cases de cette carte.

Pourquoi un framework plutôt que de simples classes

Avant Java 1.2, il existait des classes pour les groupes (Vector, Hashtable, Stack) mais pas d'interface commune — il était impossible d'écrire une méthode acceptant « n'importe quelle liste » couvrant les trois. Le Collections Framework a résolu ce problème en séparant ce qu'est un groupe (l'interface) de comment il est stocké (l'implémentation). L'avantage est visible au quotidien :

// You program against the interface, not the class.
List<String> names = new ArrayList<>();
// Later, swap in a different implementation without touching the rest of the code:
List<String> names = new LinkedList<>();

Chaque méthode appelée sur names est définie sur List. Le choix entre ArrayList et LinkedList est une décision de performance, pas d'API. On peut aussi écrire des méthodes comme void print(List<String> xs) une seule fois et y passer l'une ou l'autre implémentation.

Les quatre interfaces racines

Le framework s'organise autour de quatre interfaces racines. Choisissez celle dont le contrat correspond à la nature de vos données :

Collection<E> — la racine. Un groupe d'éléments E. Rien n'est garanti quant à l'ordre, aux doublons ou à l'indexation.
List<E> — une collection ordonnée accessible par index. Les doublons sont autorisés. Pensez « tableau qui s'agrandit » ou « séquence chaînée ». ArrayList, LinkedList, Vector.
Set<E> — une collection qui interdit les doublons. Ensemble mathématique. Peut être ordonné ou non. HashSet, LinkedHashSet, TreeSet.
Map<K, V> — association clé→valeur. Ce n'est pas une Collection (ses éléments sont des entrées, pas des valeurs isolées), mais elle fait partie du framework. HashMap, LinkedHashMap, TreeMap.

Deux autres interfaces se placent aux côtés de List et Set comme spécialisations de Collection :

Queue<E> — une collection « prochain dans la file ». FIFO par défaut. LinkedList, ArrayDeque, PriorityQueue.
Deque<E> — une file à double entrée. Ajout et suppression aux deux extrémités. ArrayDeque, LinkedList.

Chaque classe de collection de la bibliothèque standard implémente au moins une de ces interfaces.

Choisir la famille selon le comportement, puis la classe selon le coût

La décision se prend en deux étapes :

Qu'exige la donnée ? Ordonnée avec doublons → List. Sans doublons → Set. Recherche par clé → Map. Producteur/consommateur → Queue ou Deque.
Dans la famille, quels sont les patterns d'accès ? Accès aléatoire par index → ArrayList. Nombreuses insertions/suppressions en tête → LinkedList ou ArrayDeque. Itération triée → TreeSet / TreeMap. Simple « sac rapide » → HashSet / HashMap.

Un aide-mémoire pour les cas courants :

Besoin	Utiliser	Notes
Liste redimensionnable, accès aléatoire rapide	`ArrayList`	Le `List` par défaut.
Liste avec insertions/suppressions très fréquentes aux extrémités	`ArrayDeque` (comme file quasi-liste)	Surpasse `LinkedList` en pratique.
Ensemble, contains/add/remove rapides	`HashSet`	Aucune garantie d'ordre.
Ensemble avec itération prévisible	`LinkedHashSet`	Itération dans l'ordre d'insertion.
Ensemble trié	`TreeSet`	Opérations en `O(log n)`.
Map, recherche rapide	`HashMap`	La `Map` par défaut.
Map avec itération prévisible	`LinkedHashMap`	Utile pour les caches (LRU).
Map triée	`TreeMap`	Clés dans l'ordre trié.
File FIFO	`ArrayDeque`	Plus rapide que `LinkedList`.
Toujours extraire le plus petit	`PriorityQueue`	Basée sur un tas.

Vector, Stack et Hashtable sont les classes antérieures à la version 1.2 — toujours présentes dans le JDK pour la compatibilité ascendante, mais plus adaptées au nouveau code. Leurs remplaçants modernes sont traités dans leurs propres chapitres.

Les génériques rendent les collections sûres par type

Chaque interface et classe de collection est générique. On la paramètre avec le type des éléments à la déclaration, et le compilateur l'applique dès lors :

List<String> names = new ArrayList<>();
names.add("Ada");
names.add(42);          // ❌ compile error — Integer is not a String
String first = names.get(0);   // no cast needed

Le diamant <> à droite demande au compilateur d'inférer le type depuis la gauche — cela évite de le répéter sans perdre la sécurité. La partie précédente du livre (Generics) est le référentiel de toutes ces règles ; la suite de cette partie suppose que vous l'avez lue.

Les algorithmes vivent dans la classe `Collections`

Les opérations indépendantes d'une implémentation concrète — tri, mélange, inversion, recherche binaire, min, max, fréquence, enveloppes non modifiables — se trouvent dans la classe utilitaire statique java.util.Collections. Notez le s à la fin : Collection (l'interface) désigne un élément ; Collections (la classe) est la boîte à outils :

List<Integer> xs = new ArrayList<>(List.of(3, 1, 4, 1, 5, 9, 2, 6));
Collections.sort(xs);                    // mutates xs
int idx = Collections.binarySearch(xs, 5);
List<Integer> ro = Collections.unmodifiableList(xs);

Trois chapitres vers la fin de cette partie sont consacrés à Collections — recherche, tri et enveloppes non modifiables — car la classe utilitaire est le lieu où se fait une grande partie du travail concret.

Un premier tour complet

Le programme ci-dessous choisit un représentant de chaque famille et montre les opérations utilisées encore et encore. Ne vous inquiétez pas de comprendre chaque ligne maintenant — chaque classe ici aura son propre chapitre. L'objectif est de voir la forme du framework : mêmes noms de méthodes, mêmes patterns, même modèle d'itération.

java— editable, runs on the server

import java.util.*;

public class CollectionsTour {
  public static void main(String[] args) {
    // List — ordered, indexable, duplicates allowed.
    List<String> books = new ArrayList<>();
    books.add("Effective Java");
    books.add("Java Concurrency in Practice");
    books.add("Effective Java");   // duplicate is fine
    System.out.println("List:        " + books);
    System.out.println("books.get(1) = " + books.get(1));

// Set — duplicates removed silently.
    Set<String> uniqueBooks = new HashSet<>(books);
    System.out.println("Set:         " + uniqueBooks);
    System.out.println("size = " + uniqueBooks.size());

// Map — lookup by key.
    Map<String, Integer> pages = new HashMap<>();
    pages.put("Effective Java", 416);
    pages.put("Java Concurrency in Practice", 384);
    System.out.println("Map:         " + pages);
    System.out.println("pages.get(\"Effective Java\") = " + pages.get("Effective Java"));

// Queue — FIFO.
    Queue<String> printJobs = new ArrayDeque<>();
    printJobs.offer("report.pdf");
    printJobs.offer("invoice.pdf");
    System.out.println("Queue head:  " + printJobs.peek());
    System.out.println("Polled:      " + printJobs.poll());
    System.out.println("Queue now:   " + printJobs);

// Same iteration model everywhere.
    System.out.println("\nIterating the set with for-each:");
    for (String b : uniqueBooks) System.out.println("  " + b);

System.out.println("\nIterating the map's entries:");
    for (Map.Entry<String, Integer> e : pages.entrySet())
      System.out.println("  " + e.getKey() + " -> " + e.getValue() + " pages");

// Algorithms from Collections work on any List.
    Collections.sort(books);
    System.out.println("\nSorted list: " + books);
  }
}

Remarquez trois choses dans la sortie :

Le Set a silencieusement supprimé le doublon "Effective Java". C'est le contrat — aucun code supplémentaire de votre côté.
La Queue a retourné les éléments dans l'ordre d'insertion. offer met en file, peek consulte la tête sans la retirer, poll la retire et la retourne.
La boucle for-each fonctionne sur toute Collection. Les Map s'itèrent via entrySet(), keySet() ou values() selon ce que l'on veut.

C'est le framework en miniature.

Avertissement

HashSet et HashMap ne garantissent aucun ordre d'itération — l'ordre visible dans la sortie ci-dessus est un détail d'implémentation qui peut varier selon la version de la JVM ou l'exécution. Si vous avez besoin d'un ordre stable, utilisez LinkedHashSet/LinkedHashMap (ordre d'insertion) ou TreeSet/TreeMap (ordre trié). N'écrivez jamais de code qui dépend de l'ordre d'itération d'un simple HashSet ou HashMap.

Et maintenant

Vous avez vu la carte. La suite de la partie 11 explore chaque région. Le point de départ naturel est la racine dont hérite toute collection — l'interface Collection elle-même, où des méthodes comme add, remove, contains, size et iterator() sont définies une fois pour toutes.

Pratique

Vous devez stocker un groupe de mots et répondre rapidement à la question : 'ce mot est-il dans le groupe ?' Les doublons n'ont pas d'intérêt — `cat` est présent ou non. Quelle famille du Collections Framework convient le mieux ?

`Set` — il interdit les doublons et est conçu pour des tests d'appartenance rapides (`contains` est en `O(1)` en moyenne sur un `HashSet`)`List` — `contains(x)` est la méthode standard pour vérifier l'appartenance et fonctionne sur toute liste`Map` — on utiliserait le mot comme clé et `null` comme valeur`Queue` — on ferait `peek` en boucle jusqu'à trouver le mot ou atteindre la fin