Choisir sa collection

Publié le 21/10/2026 · Mis à jour le 21/10/2026

Le problème

Un import vérifie, pour chacune des 200 000 lignes reçues, si le nom figure déjà dans les données connues :

List<String> connus = chargerNoms(); // 500 000 noms

for (String nom : lignes) {
    if (!connus.contains(nom)) {     // ⚠️ parcours complet de la liste à chaque appel
        connus.add(nom);
    }
}

List.contains compare l'élément à chaque entrée jusqu'à le trouver : O(n). Sur 200 000 recherches dans une liste d'un demi-million d'éléments, cela fait des dizaines de milliards de comparaisons, et le traitement passe de quelques millisecondes à plusieurs minutes. Le même code avec un HashSet effectue un calcul de hash par recherche. Choisir la collection, c'est choisir les complexités de ses opérations.

Les trois familles

Interface	Ce qu'elle modélise	Doublons	Accès
`List`	Une séquence ordonnée	Autorisés	Par index
`Set`	Un ensemble d'éléments uniques	Interdits	Par appartenance
`Map`	Des associations clé → valeur	Clés uniques	Par clé

La question à se poser : quelle opération sera la plus fréquente ? Parcourir dans l'ordre, accéder par position, tester l'appartenance, retrouver par clé ?

Complexités des implémentations courantes

Opération	`ArrayList`	`LinkedList`	`HashSet` / `HashMap`	`TreeSet` / `TreeMap`
Ajout en fin	O(1) amorti	O(1)	O(1) moyen	O(log n)
Accès par index	O(1)	O(n)	—	—
`contains` / `get(clé)`	O(n)	O(n)	O(1) moyen	O(log n)
Suppression au milieu	O(n)	O(n) pour trouver, O(1) pour retirer	O(1) moyen	O(log n)
Ordre d'itération	Insertion	Insertion	Aucun garanti	Trié

Variantes à connaître :

LinkedHashSet / LinkedHashMap : performances d'un Hash* avec l'ordre d'insertion préservé.
ArrayDeque : pile ou file, plus rapide que LinkedList et que l'ancienne Stack.
EnumMap / EnumSet : clés de type enum, stockage en tableau, très compacts.

En pratique, LinkedList est rarement le bon choix : chaque nœud est un objet séparé, dispersé en mémoire, et les caches du processeur s'en accommodent mal. ArrayList gagne presque toujours, même pour des insertions.

Le correctif de l'import

Set<String> connus = new HashSet<>(chargerNoms()); // ✅ construit une fois

for (String nom : lignes) {
    connus.add(nom); // add renvoie false si le nom existe déjà, inutile de tester avant
}

Construire le HashSet a un coût O(n) : la conversion n'est rentable que si plusieurs recherches suivent. Pour une seule recherche, la liste suffit.

Capacité initiale

`ArrayList`

Une ArrayList repose sur un tableau. Créée sans argument, elle alloue un tableau de 10 cases au premier ajout, puis, chaque fois qu'il est plein, un nouveau tableau environ 1,5 fois plus grand dans lequel elle recopie tout. Pour un million d'éléments, cela représente une trentaine de réallocations et autant de tableaux à collecter par le GC.

List<President> resultat = new ArrayList<>(source.size()); // ✅ une seule allocation
for (Ligne l : source) {
    resultat.add(convertir(l));
}

List<President> copie = new ArrayList<>(source2); // ✅ déjà dimensionnée
List<President> figee = List.copyOf(source2);     // ✅ copie immuable

`HashMap` et `HashSet`

Une HashMap se redimensionne quand le nombre d'entrées dépasse capacité × facteur de charge (0,75 par défaut). Le piège : new HashMap<>(1000) ne contient pas 1 000 entrées sans redimensionnement, puisque le seuil est de 1 024 × 0,75 = 768.

Map<String, Integer> m1 = new HashMap<>(1000);       // ⚠️ un redimensionnement à 769 entrées
Map<String, Integer> m2 = HashMap.newHashMap(1000);  // ✅ Java 19+ : calibrée pour 1 000 entrées
Set<String> s = HashSet.newHashSet(1000);            // ✅ Java 19+

`equals` et `hashCode` : le contrat des collections hachées

HashSet et HashMap rangent un objet selon son hashCode(), puis comparent avec equals(). Deux objets égaux doivent avoir le même hash. Sans redéfinition, ce sont les méthodes d'Object qui s'appliquent, basées sur l'identité.

class Fiche {
    String nom; int annee;
    Fiche(String nom, int annee) { this.nom = nom; this.annee = annee; }
    // ❌ ni equals ni hashCode
}

Set<Fiche> set = new HashSet<>();
set.add(new Fiche("Paul Doumer", 1931));
set.contains(new Fiche("Paul Doumer", 1931)); // false 💥 deux identités différentes

Un record génère equals, hashCode et toString à partir de ses composants :

record President(String nom, int annee) {}

Set<President> set = new HashSet<>();
set.add(new President("Paul Doumer", 1931));
set.contains(new President("Paul Doumer", 1931)); // true ✅

Pour une classe classique, redéfinis les deux méthodes sur les mêmes champs, avec Objects.hash et Objects.equals.

Les collections triées (TreeSet, TreeMap) n'utilisent pas hashCode mais compareTo ou un Comparator : deux éléments qui comparent à 0 sont considérés comme identiques.

Set<President> parAnnee = new TreeSet<>(Comparator.comparingInt(President::annee));
parAnnee.add(new President("Paul Deschanel", 1920));
parAnnee.add(new President("Alexandre Millerand", 1920)); // ⚠️ ignoré : même année

Collections immuables et séquencées

List.of, Set.of et Map.of (Java 9+) créent des collections immuables, qui refusent les null. Toute modification lève UnsupportedOperationException. Depuis Java 21, List, Deque, LinkedHashSet et LinkedHashMap implémentent les interfaces séquencées : getFirst(), getLast(), reversed().

List<String> noms = List.of("Gaston Doumergue", "Paul Doumer", "Albert Lebrun");
noms.getLast(); // "Albert Lebrun", Java 21

Ce qu'il ne faut PAS faire

❌ Tester l'appartenance dans une grande List en boucle. contains et indexOf sont en O(n). Convertis une fois en HashSet si les recherches se répètent.
❌ Mettre en HashSet une classe sans equals/hashCode. Les doublons logiques ne sont pas détectés et contains renvoie false. Utilise un record ou redéfinis les deux méthodes ensemble.
❌ Modifier un objet après l'avoir utilisé comme clé. Si un champ qui entre dans hashCode change, l'objet reste rangé dans l'ancien compartiment : il devient introuvable et ne peut plus être retiré. Les clés doivent être immuables.
```
record Cle(String nom, int annee) {} // ✅ composants final
```
❌ Supprimer pendant un for-each. Modifier la collection pendant son parcours lève ConcurrentModificationException.
```
presidents.removeIf(p -> p.annee() < 1900); // ✅
```
❌ Choisir LinkedList « pour les insertions ». L'accès au point d'insertion est déjà en O(n) et la localité mémoire est mauvaise. ArrayList ou ArrayDeque font mieux dans l'immense majorité des cas.
❌ Réutiliser une liste stockée en champ comme tampon entre deux appels. Les éléments s'accumulent d'un appel à l'autre : doublons et fuite mémoire. Crée la liste localement dans la méthode.

À retenir

List pour l'ordre et l'index, Set pour l'unicité et l'appartenance, Map pour l'accès par clé.
contains est en O(n) sur une List, O(1) en moyenne sur un HashSet, O(log n) sur un TreeSet.
Quand la taille est connue : new ArrayList<>(n) et HashMap.newHashMap(n) (Java 19+).
Toute clé de collection hachée doit redéfinir equals et hashCode de façon cohérente et rester immuable ; un record le fait pour toi.