Recherche dans les collections Java

« Cet élément est-il dans la collection ? » semble être une seule question, mais Java y répond d'une demi-douzaine de façons différentes, avec des coûts différents et des types de retour différents. Savoir lequel utiliser peut transformer une boucle critique de 50 millisecondes en 50 microsecondes. Ce chapitre est un tour d'horizon des méthodes de recherche sur les collections, les maps qui les encapsulent, et les helpers statiques de Collections.

Le modèle mental basé sur le coût

Le coût de chaque méthode de recherche est déterminé par la collection sous-jacente, et non par le site d'appel. Choisissez la bonne collection dès le départ et vos recherches seront gratuites ; choisissez la mauvaise et aucune méthode astucieuse ne vous sauvera.

Collection	`contains` / lookup	Pourquoi
`HashSet`, `LinkedHashSet`, `HashMap.keySet()`	O(1) attendu	Lookup dans un bucket de hachage
`TreeSet`, `TreeMap.keySet()`	O(log n)	Arbre rouge-noir
`ArrayList`, `LinkedList`, `Vector`	O(n)	Balayage linéaire
`ArrayList` trié + `Collections.binarySearch`	O(log n)	Recherche binaire sur une liste indexée
`LinkedList` + `Collections.binarySearch`	O(n)	La recherche binaire doit indexer — O(n) par étape

Deux règles empiriques :

Si vous appelez contains souvent, utilisez un Set. Construire un HashSet à partir d'une List et l'interroger est presque toujours plus rapide que list.contains dans une boucle.
Si les données sont triées et indexées, utilisez Collections.binarySearch. Cela devient rentable à partir d'environ 30 éléments sur la plupart des JVM.

`Collection.contains(o)`

Toutes les Collection le possèdent. La sémantique est basée sur l'égalité :

boolean has = list.contains("alpha");        // uses .equals

Pour une List, il s'agit d'un balayage linéaire — O(n). Pour un HashSet, c'est un lookup dans un bucket de hachage — O(1) attendu. Pour un TreeSet, c'est un parcours d'arbre en O(log n). La signature de la méthode est la même ; le coût ne l'est pas.

null est autorisé (la méthode retourne si la collection contient un élément null), sauf si la collection rejette null catégoriquement — TreeSet avec l'ordre naturel, EnumSet, ConcurrentHashMap.keySet().

`List.indexOf` et `lastIndexOf`

Les listes prennent en charge plus que le simple « oui/non » — elles retournent la position :

int firstA = list.indexOf("alpha");          // -1 if absent
int lastA  = list.lastIndexOf("alpha");

Balayage linéaire depuis le début (ou la fin). Pour un ArrayList<String> de mille éléments, c'est acceptable. Pour un million, construisez une Map<String, Integer> une fois et interrogez-la.

`Map.containsKey`, `containsValue`, `get`, `getOrDefault`

Les méthodes de recherche propres aux maps se divisent clairement :

map.containsKey("alpha");                    // O(1) for HashMap, O(log n) for TreeMap
map.get("alpha");                             // returns the value or null
map.getOrDefault("alpha", 0);                 // returns the value or your default
map.containsValue("v");                       // O(n) — scans every entry

containsValue est le piège. Elle parcourt chaque entrée à chaque fois. Si vous vous retrouvez à l'appeler plusieurs fois, construisez une map inverse (Map<V, K>) ou un Set<V> de valeurs une fois et interrogez-le.

getOrDefault est un petit mais important changement de paradigme : il remplace l'ancien idiome Integer n = map.get(k); if (n == null) n = 0; par une seule ligne, et la valeur par défaut n'est utilisée que quand la clé est absente — pas quand la valeur est null. (Pour « absent ou null », utilisez Objects.requireNonNullElse(map.get(k), 0).)

`Collections.binarySearch`

Recherche binaire sur une liste triée :

List<String> sorted = new ArrayList<>(...);
Collections.sort(sorted);
int hit  = Collections.binarySearch(sorted, "delta");      // 2  (some index)
int miss = Collections.binarySearch(sorted, "zeta");       // negative

Deux prérequis :

La liste doit être triée dans l'ordre utilisé par la recherche. Si vous avez trié avec un comparateur, passez le même comparateur à binarySearch. Des ordres incompatibles produisent des résultats incohérents (silencieusement — pas d'exception).
La liste devrait être indexée (ArrayList, pas LinkedList). Sur une liste chaînée, la recherche binaire est en O(n log n), ce qui est pire qu'un balayage linéaire.

La valeur de retour encode à la fois « trouvé » et « où insérer » :

int i = Collections.binarySearch(sorted, key);
if (i >= 0) {
  // key is at index i
} else {
  int insertAt = -i - 1;
  sorted.add(insertAt, key);             // keeps the list sorted
}

L'arithmétique -i - 1 est la façon dont chaque routine « trouver ou insérer » dans le JDK gère un échec. Cela vaut la peine d'être mémorisé.

`Collections.frequency` et `disjoint`

Deux helpers qui encapsulent des patterns de recherche courants :

int n = Collections.frequency(coll, "alpha");        // how many times "alpha" appears
boolean none = Collections.disjoint(a, b);           // no element of a is in b

frequency est O(n). Pour des requêtes répétées avec différentes cibles, comptez une fois avec un stream dans une Map<T, Long>.

disjoint est implémenté intelligemment : il itère sur la collection la plus petite et vérifie contains sur la plus grande si celle-ci est un Set, en échangeant les arguments en coulisses. Ainsi, Collections.disjoint(largeList, smallSet) est O(largeList) — et plus rapide que de l'implémenter soi-même.

Recherche basée sur les streams

Les streams gèrent « trouver le premier élément correspondant » avec findFirst / findAny, et « y a-t-il une correspondance » avec anyMatch / allMatch / noneMatch :

Optional<Person> match = people.stream()
    .filter(p -> p.age() >= 18 && p.name().startsWith("A"))
    .findFirst();

boolean any = people.stream().anyMatch(p -> p.age() >= 65);
boolean all = people.stream().allMatch(p -> p.age() >= 0);
boolean non = people.stream().noneMatch(p -> p.age() < 0);

Les streams court-circuitent sur findFirst et anyMatch — ils s'arrêtent dès qu'une correspondance est trouvée. Ce sont les réponses les plus claires pour une recherche basée sur un prédicat. Ils ne sont pas plus rapides que contains pour une recherche par égalité sur la bonne structure de données — un HashSet.contains battra toujours stream().anyMatch(x -> x.equals(target)).

Optional<T> mérite une attention particulière (il a un chapitre dans la partie programmation fonctionnelle). Pour l'instant : findFirst().isPresent() est l'expression la plus claire pour « avons-nous trouvé quelque chose ? » pour un prédicat.

`LinkedHashSet` pour « contains et ordre »

Un pattern courant : vous avez besoin d'un contains rapide et d'une itération dans l'ordre d'insertion. LinkedHashSet est la réponse :

LinkedHashSet<String> seen = new LinkedHashSet<>();
for (String line : input) {
  if (seen.add(line)) System.out.println(line);    // print first occurrences only
}

add retourne true uniquement la première fois. L'ensemble rejette les doublons en O(1) et préserve l'ordre d'insertion pour l'itération. C'est le bon outil pour « dédupliquer tout en conservant l'ordre » — ni HashSet (perd l'ordre) ni ArrayList (contains lent) n'est aussi adapté.

Exemple concret : comparaison de cinq stratégies de recherche sur les mêmes données

Le programme ci-dessous charge 100 000 chaînes dans différentes collections et chronomètre cinq stratégies de recherche pour 1 000 accès aléatoires : ArrayList.contains, HashSet.contains, TreeSet.contains, Collections.binarySearch sur une liste triée, et stream().anyMatch.

java— editable, runs on the server

import java.util.*;
import java.util.stream.*;

public class SearchingShowcase {
  public static void main(String[] args) {
    int N = 100_000;
    int Q = 1_000;
    List<String> data = new ArrayList<>(N);
    for (int i = 0; i < N; i++) data.add("k" + i);

// Build the same data in several shapes
    HashSet<String>   asHash   = new HashSet<>(data);
    TreeSet<String>   asTree   = new TreeSet<>(data);
    List<String>      sortedAL = new ArrayList<>(data);
    Collections.sort(sortedAL);

// Pick Q random keys to look up
    Random rng = new Random(7);
    List<String> queries = IntStream.range(0, Q)
        .mapToObj(i -> "k" + rng.nextInt(N))
        .toList();

long t1 = System.nanoTime();
    int hits1 = 0;
    for (String q : queries) if (data.contains(q)) hits1++;
    long durList = System.nanoTime() - t1;

long t2 = System.nanoTime();
    int hits2 = 0;
    for (String q : queries) if (asHash.contains(q)) hits2++;
    long durHash = System.nanoTime() - t2;

long t3 = System.nanoTime();
    int hits3 = 0;
    for (String q : queries) if (asTree.contains(q)) hits3++;
    long durTree = System.nanoTime() - t3;

long t4 = System.nanoTime();
    int hits4 = 0;
    for (String q : queries) if (Collections.binarySearch(sortedAL, q) >= 0) hits4++;
    long durBin = System.nanoTime() - t4;

long t5 = System.nanoTime();
    int hits5 = 0;
    for (String q : queries) if (data.stream().anyMatch(q::equals)) hits5++;
    long durStream = System.nanoTime() - t5;

System.out.println("strategy             hits   time (ms)");
    System.out.println("-----------------------------------");
    System.out.printf("ArrayList.contains  %5d   %d%n", hits1, durList   / 1_000_000);
    System.out.printf("HashSet.contains    %5d   %d%n", hits2, durHash   / 1_000_000);
    System.out.printf("TreeSet.contains    %5d   %d%n", hits3, durTree   / 1_000_000);
    System.out.printf("binarySearch (AL)   %5d   %d%n", hits4, durBin    / 1_000_000);
    System.out.printf("stream.anyMatch     %5d   %d%n", hits5, durStream / 1_000_000);

// --- The missing-key arithmetic: -i - 1 is the insertion point ---
    int miss = Collections.binarySearch(sortedAL, "zzz");
    int insertAt = -miss - 1;
    System.out.println("\nbinarySearch('zzz') = " + miss
        + "   insertAt = " + insertAt
        + "   list size = " + sortedAL.size() + "   (would append at end)");
  }
}

Ce qu'il faut retenir de l'exécution :

HashSet.contains et Collections.binarySearch sur l'ArrayList triée sont nettement plus rapides qu'ArrayList.contains pour les recherches répétées. La table de hachage gagne pour « toute égalité », la recherche binaire gagne quand les données doivent être maintenues triées pour d'autres raisons.
TreeSet.contains est juste derrière, mais pas gratuit — chaque lookup parcourt un arbre de profondeur ~log₂(100 000) ≈ 17, avec des défauts de cache pour les pointeurs d'arbre.
stream().anyMatch pour la recherche par égalité est la pire option ici : même O(n) que list.contains mais avec un overhead d'allocation supplémentaire par requête. Utilisez-le pour les prédicats, pas pour l'égalité simple sur une liste.
L'appel avec une clé manquante a retourné une valeur négative, et -i - 1 a donné l'index où "zzz" serait inséré pour conserver la liste triée. C'est la même convention que TreeMap.subMap et Arrays.binarySearch utilisent.

Et ensuite

Vous avez maintenant couvert l'itération, l'ordonnancement, le tri et la recherche — les quatre opérations mécaniques que le framework de collections existe pour faciliter. Le dernier chapitre de cette partie est l'histoire moderne pour la seule chose qu'aucun d'eux n'a abordée : l'immutabilité. Les collections non modifiables Java couvre List.of, Set.of, Map.of, et les wrappers Collections.unmodifiable* — quand chacun est le bon choix, et pourquoi un pattern de « copie défensive » qui prenait autrefois quatre lignes tient désormais en une seule.

Pratique

Vous appelez `Collections.binarySearch(sortedList, key)` et le résultat est `-5`. À quel index faudrait-il insérer `key` pour conserver la liste triée ?

`4` — pour un échec, le point d'insertion est `-result - 1``-5` — les collections Java prennent en charge les indices négatifs pour les insertions après recherche binaire`5` — la valeur absolue du résultat négatif est le point d'insertion`0` — un résultat négatif signifie que la liste n'est pas triée et que la recherche a été interrompue avant de trouver une position

Le modèle mental basé sur le coût

Collection.contains(o)

List.indexOf et lastIndexOf

Map.containsKey, containsValue, get, getOrDefault

Collections.binarySearch

Collections.frequency et disjoint