Algorithmes de collections Java

Les algorithmes de collections Java font référence àjava.util.Collectionsun ensemble de méthodes statiques fournies dans la classe Collections, utilisées pour effectuer des opérations courantes telles que le tri, la recherche, le mélange, le remplissage, etc. sur des collections (List, Set, Map, etc.).

Ces algorithmes sont intégrés au JDK et sont hautement optimisés. Les développeurs n'ont pas besoin de les écrire à partir de zéro ; ils peuvent simplement les appeler directement.

Aperçu des algorithmes de collections

java.util.CollectionsCollections est une classe utilitaire ; toutes ses méthodes sont statiques, similaire à la classe utilitaire Arrays pour les tableaux.

Le tableau suivant répertorie les algorithmes de collection les plus couramment utilisés et leurs objectifs :

Catégorie d'algorithme	Nom de la méthode	Description
Tri	sort()	Trie une List par ordre croissant
Mélange	shuffle()	Mélange de manière aléatoire l'ordre des éléments d'une List
Inversion	reverse()	Inverse l'ordre des éléments dans une List
Recherche binaire	binarySearch()	Effectue une recherche binaire pour un élément spécifié dans une List triée
Remplissage	fill()	Remplace tous les éléments d'une List par un élément spécifié
Copy	copy()	Copie les éléments d'une List vers une autre List
Maximum/Minimum	max() / min()	Renvoie l'élément maximum ou minimum dans une collection
Comptage des fréquences	frequency()	Renvoie le nombre d'occurrences d'un élément spécifié dans une collection
Vérification de disjonction	disjoint()	Détermine si deux collections ont des éléments communs
Collection immuable	unmodifiableXxx()	Renvoie une vue en lecture seule d'une collection
Sécurité des threads	synchronizedXxx()	Renvoie un wrapper thread-safe pour une collection

Tri

Collections.sort()C'est l'algorithme de collection le plus couramment utilisé, qui trie les éléments d'une List par ordre croissant.

Sous le capot, il utilise un tri fusion optimisé (TimSort), avec une complexité temporelle en O(n log n) et des performances stables.

Le processus de tri est illustré dans la figure suivante :

Tri par ordre naturel

Lorsque la classe des éléments implémenteComparablel'interface, vous pouvez appeler directement sort() pour trier par ordre naturel.

Exemple

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SortExample {
public static void main(String[] args) {
List<String> names = new ArrayList<>();
names.add("example");
names.add("EXAMPLE");
names.add("apple");
names.add("banana");

System.out.println("Before sorting: " + names);

// Trier par ordre naturel (par point de code Unicode)
Collections.sort(names);

System.out.println("Après tri : " + names);
}
}

Résultat de sortie :

排序前: [example, EXAMPLE, apple, banana]
排序后: [EXAMPLE, apple, banana, example]

Tri personnalisé avec Comparator

En utilisantComparator, vous pouvez trier selon n'importe quelle règle personnalisée sans modifier la classe de l'élément elle-même.

Exemple : Trier par longueur de String

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class CustomSortExample {
public static void main(String[] args) {
List<String> words = new ArrayList<>();
words.add("example");
words.add("java");
words.add("algorithm");
words.add("C");

System.out.println("Avant le tri : " + words);

// Trier par longueur de chaîne dans l'ordre croissant
Collections.sort(words, new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
return s1.length() - s2.length();
}
});

System.out.println("Après tri par longueur : " + words);
}
}

Résultat de sortie :

排序前: [example, java, algorithm, C]
按长度排序后: [C, java, example, algorithm]

Java 8+ peut utiliser des expressions Lambda pour simplifier le code :

Exemple : syntaxe Lambda

// Trier par longueur en utilisant une expression Lambda
Collections.sort(words, (s1, s2) -> s1.length() - s2.longueur());

// Ou utiliser Comparator.comparingInt
Collections.sort(words, Comparator.comparingInt(String::longueur));

// Tri inversé
Collections.sort(words, Comparator.reverseOrder());

// Trier par longueur en ordre inverse
Collections.sort(words, Comparator.comparingInt(String::length).reversed());

Mélange

Collections.shuffle()Utilise l'algorithme de Fisher-Yates pour mélanger aléatoirement l'ordre des éléments d'une List.

Exemple

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ShuffleExample {
public static void main(String[] args) {
List<Integer> numbers = new ArrayList<>();
for (int i = 1; i <= 10; i++) {
numbers.add(i);
}

System.out.println("Liste originale : " + numbers);

// Mélanger aléatoirement l'ordre
Collections.shuffle(numbers);
System.out.println("Premier mélange : " + numbers);

Collections.shuffle(numbers);
System.out.println("Deuxième mélange : " + numbers);
}
}

Résultat de sortie :

原始列表: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
第一次混排: [7, 3, 9, 1, 5, 10, 8, 2, 4, 6]
第二次混排: [4, 10, 1, 8, 6, 3, 2, 9, 5, 7]

Recherche binaire

Collections.binarySearch()Utilise l'algorithme de recherche binaire pour localiser un élément cible dans une List triée.

La complexité temporelle est O(log n), bien meilleure que le O(n) d'un parcours linéaire.

Prérequis important : la List doit déjà être triée par ordre croissant ; sinon, le résultat est indéfini.

Exemple

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BinarySearchExample {
public static void main(String[] args) {
List<Integer> numbers = new ArrayList<>();
numbers.add(10);
numbers.add(30);
numbers.add(20);
numbers.add(50);
numbers.add(40);

// Il faut d'abord trier
Collections.sort(numbers);
System.out.println("Liste triée : " + numbers);

// Recherche binaire : la valeur de retour est l'index (>= 0 signifie trouvé)
int index = Collections.binarySearch(numbers, 30);
System.out.println("Position de l'index de 30 : " + index);

// Recherche d'un élément inexistant : renvoie une valeur négative = -(point d'insertion) - 1
int notFound = Collections.binarySearch(numbers, 25);
System.out.println("Valeur de retour pour 25 (introuvable) : " + notFound);
// Point d'insertion = -(notFound + 1) = 2, il devrait donc être inséré à l'index 2
}
}

Résultat de sortie :

排序后列表: [10, 20, 30, 40, 50]
30 的索引位置: 2
25 的返回值（不存在）: -3

Lorsque binarySearch() ne trouve pas un élément, elle renvoie une valeur négative, la formule est-(point d'insertion) - 1Le point d'insertion est l'index où l'élément serait situé s'il existait. L'astuce de cette conception est que si l'élément existe, un index non négatif est renvoyé ; s'il n'existe pas, une valeur négative est inévitablement renvoyée, donc il n'y a pas d'ambiguïté.

Maximum et minimum

Collections.max()etCollections.min()Renvoie l'élément maximum/minimum d'une collection selon l'ordre naturel ou un comparateur spécifié.

Exemple

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class MaxMinExample {
public static void main(String[] args) {
List<String> words = new ArrayList<>();
words.add("example");
words.add("algorithm");
words.add("java");
words.add("code");

// Obtenir le maximum et le minimum par ordre naturel (ordre lexicographique)
String maxWord = Collections.max(words);
String minWord = Collections.min(words);
System.out.println("Maximum lexicographique : " + maxWord);
System.out.println("Minimum lexicographique : " + minWord);

// Obtenir le maximum et le minimum par longueur de chaîne
String longest = Collections.max(words,
Comparator.comparingInt(String::length));
String shortest = Collections.min(words,
Comparator.comparingInt(String::length));
System.out.println("Longueur maximale: " + longest);
System.out.println("Longueur minimale: " + shortest);
}
}

Résultat de sortie :

字典序最大: example
字典序最小: algorithm
长度最长: algorithm
长度最短: code

Comptage de fréquence et vérification de disjonction

Collections.frequency()Compte le nombre d'occurrences d'un élément spécifié dans une collection.

Collections.disjoint()Détermine si deux collections n'ont aucun élément en commun du tout.

Exemple

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class FrequencyDisjointExample {
public static void main(String[] args) {
List<String> items = new ArrayList<>();
items.add("example");
items.add("java");
items.add("example");
items.add("python");
items.add("example");

// Compter les occurrences de "example"
int count = Collections.frequency(items, "example");
System.out.println("\"example\""Occurrences: " + count);

// Vérifier si les deux collections sont disjointes
List<String> groupA = new ArrayList<>();
groupA.add("java");
groupA.add("python");

List<String> groupB = new ArrayList<>();
groupB.add("C++");
groupB.add("go");

boolean noCommon = Collections.disjoint(groupA, groupB);
System.out.println("groupA et groupB sont : " + noCommon);
}
}

Résultat de sortie :

"example" 出现次数: 3
groupA 与 groupB 不相交: true

Collections immuables et wrappers thread-safe

Collections fournit des méthodes pour envelopper des collections ordinaires en collections immuables ou en collections thread-safe.

Collections immuables (non modifiables)

En appelantCollections.unmodifiableList()et d'autres méthodes, on peut créer une vue en lecture seule.

Toute opération de modification lancera UnsupportedOperationException.

Collections thread-safe (synchronisées)

En appelantCollections.synchronizedList()et d'autres méthodes, on peut créer un wrapper thread-safe.

Dans un environnement multithread, les appels individuels aux méthodes sur ces collections sont sûrs, mais les opérations composées nécessitent encore une synchronisation externe.

Exemple

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class WrapperExample {
public static void main(String[] args) {
List<String> original = new ArrayList<>();
original.add("example");
original.add("java");

// Créer une vue immuable
List<String> readOnly = Collections.unmodifiableList(original);
System.out.println("Vue immuable : " + readOnly);

// readOnly.add("error"); // L'exécution de ceci lèvera une exception

// Après modification de la liste d'origine, la vue immuable reflète également les modifications
original.add("python");
System.out.println("Après modification de l'original : " + readOnly);

// Créer un wrapper thread-safe
List<String> syncList = Collections.synchronizedList(
new ArrayList<>());
syncList.add("thread-safe");

// Une synchronisation manuelle est nécessaire lors de l'itération
synchronized (syncList) {
for (String item : syncList) {
System.out.println(item);
}
}
}
}

Résultat de sortie :

不可变视图: [example, java]
原始修改后: [example, java, python]
thread-safe

Une vue immuable empêche uniquement de modifier la collection via cette vue ; la collection sous-jacente reste mutable. Si vous avez besoin d'une collection vraiment immuable, utilisezList.of(),、Set.of() de Java 9+.et d'autres méthodes.

Opérations algorithmiques courantes en un coup d'œil

Ce qui suit résume les méthodes d'appel et les complexités temporelles des algorithmes courants dans Collections :

Opération	Appel de méthode	Complexité temporelle	Prérequis
Tri	Collections.sort(list)	O(n log n)	Les éléments implémentent Comparable
Tri personnalisé	Collections.sort(list, comp)	O(n log n)	Fournir un Comparator
Inversion	Collections.reverse(list)	O(n)	Aucune
Mélange	Collections.shuffle(list)	O(n)	Aucune
Recherche binaire	Collections.binarySearch(list, key)	O(log n)	La liste est triée
Remplissage	Collections.fill(list, obj)	O(n)	Aucune
Copie	Collections.copy(dest, src)	O(n)	dest.size() >= src.size()
Maximum	Collections.max(coll)	O(n)	Les éléments implémentent Comparable
Minimum	Collections.min(coll)	O(n)	Les éléments implémentent Comparable
Comptage de fréquence	Collections.frequency(coll, obj)	O(n)	Aucune
Échange d'éléments	Collections.swap(list, i, j)	O(1)	Les indices sont valides
Rotation	Collections.rotate(list, distance)	O(n)	Aucune

Notes

binarySearch() doit être appelée sur une liste triée ; le résultat renvoyé pour une liste non triée n'est pas défini. Si la liste contient des éléments dupliqués, il n'y a aucune garantie quant à celui qui sera trouvé.

Le wrapper renvoyé par synchronizedXxx() ne garantit l'atomicité qu'au niveau d'un seul appel de méthode. Les opérations composées (telles que if(!list.contains(x)) list.add(x)) nécessitent toujours un bloc synchronized externe.

Différence entre sort() et List.sort() :

Depuis Java 8, l'interface List a ajouté la méthode par défaut sort(Comparator).

list.sort(null) trie selon l'ordre naturel, équivalent à Collections.sort(list).

Les deux ont la même implémentation sous-jacente, mais list.sort() est plus concis syntaxiquement.

Suggestions de comparaison des performances :

Pour de petits volumes de données (moins de 100 éléments), les différences de performance entre les différents algorithmes sont négligeables.

Pour de grands volumes de données, binarySearch() est nettement supérieur à la recherche linéaire de indexOf().

Lorsque des recherches fréquentes sont nécessaires, envisagez d'utiliser HashSet au lieu de List, car la complexité de recherche est O(1).

Autres extensions

Java Orienté objet

Java Tutoriel avancé

Algorithmes de collections Java

Aperçu des algorithmes de collections

Tri

Tri par ordre naturel

Exemple

Tri personnalisé avec Comparator

Exemple : Trier par longueur de String

Exemple : syntaxe Lambda

Mélange

Exemple

Recherche binaire

Exemple

Maximum et minimum

Exemple

Comptage de fréquence et vérification de disjonction

Exemple

Collections immuables et wrappers thread-safe

Collections immuables (non modifiables)

Collections thread-safe (synchronisées)

Exemple

Opérations algorithmiques courantes en un coup d'œil

Notes