Interface Set en Java

Set<E> est une Collection<E> avec une règle supplémentaire : pas de doublons. L'interface elle-même n'ajoute presque aucune nouvelle méthode — elle hérite de add, remove, contains, size, iterator et du reste. Ce qu'elle change, c'est ce que ces méthodes garantissent : add(e) retourne false (et ne modifie rien) si un élément égal est déjà dans le set ; deux sets sont equals s'ils contiennent les mêmes éléments indépendamment de l'ordre ; et hashCode est la somme des hashes des éléments, de sorte que des sets égaux s'accordent toujours.

Ce petit contrat — « les éléments sont uniques » — s'avère être exactement ce dont vous avez besoin pour les tests d'appartenance, la déduplication, l'intersection/union et mille autres motifs qui se lisent mal avec une List.

Ce qui constitue un doublon

Un Set détermine les doublons via equals (et, dans les sets basés sur le hachage, hashCode comme fonction de compartimentage). Ce n'est pas l'égalité de pointeur, ni « semble identique à l'impression ». Si vous placez votre propre classe dans un Set, vous devez redéfinir les deux méthodes ensemble ; le chapitre equals et hashCode a couvert le contrat.

Set<String> tags = new HashSet<>();
tags.add("java");
tags.add("java");      // add returns false; the set still has one element
tags.add(new String("java")); // also false — equals, not reference

Un piège courant : stocker des éléments mutables et les muter alors qu'ils se trouvent dans un set basé sur le hachage. Le hash de l'élément change, le set le cherche dans le mauvais compartiment, et contains commence à mentir. La règle : si vous placez un objet dans un hash set, considérez-le comme effectivement immuable à partir de ce moment. TreeSet présente le même piège avec compareTo.

Les quatre implémentations standard

java.util fournit quatre implémentations de Set qui couvrent presque tous les cas d'usage :

Les trois premières sont couvertes dans les trois chapitres suivants ; EnumSet est couvert plus loin dans le livre aux côtés d'EnumMap.

Les opérations en masse : union, intersection, différence

Un Set hérite de quatre opérations en masse de Collection, et sur un Set elles prennent le sens de la théorie des ensembles :

• addAll(other) — union (en place). Après l'appel, a contient chaque élément de l'un ou l'autre côté.
• retainAll(other) — intersection (en place). Après l'appel, a contient uniquement les éléments qui étaient aussi dans other.
• removeAll(other) — différence (en place). Après l'appel, a contient uniquement les éléments qui n'étaient pas dans other.
• containsAll(other) — test de sous-ensemble. Retourne true si chaque élément de other est dans a.

Ces opérations mutent le récepteur. Si vous avez besoin d'une version non destructive, copiez d'abord : Set<E> u = new HashSet<>(a); u.addAll(b);.

Égalité et codes de hachage des sets

Le contrat de Set pour equals est inhabituel : deux sets sont égaux s'ils contiennent les mêmes éléments, indépendamment de l'ordre ou du type d'implémentation. Un HashSet, un LinkedHashSet et un TreeSet contenant les mêmes éléments se comparent tous comme égaux entre eux.

Set<Integer> a = new HashSet<>(List.of(1, 2, 3));
Set<Integer> b = new TreeSet<>(List.of(3, 2, 1));
System.out.println(a.equals(b));   // true

C'est pourquoi les opérations en masse et les méthodes de fabrique immuables peuvent passer librement d'une implémentation à l'autre — seule la règle « mêmes éléments » est observée.

Fabriques en lecture seule et immuables

Depuis Java 9, le moyen le plus simple de créer un petit set fixe est Set.of(...) :

Set<String> primary = Set.of("red", "green", "blue");

Set.of retourne un set immuable qui refuse les éléments null et lève une exception si vous passez un doublon lors de la construction. Pour un instantané défensif d'un set existant, utilisez Set.copyOf(existing) — également immuable, également rejette les null.

Pour une vue qui masque les mutations (l'original peut toujours être modifié, mais les appelants ne peuvent pas ajouter à travers la vue), utilisez Collections.unmodifiableSet(s). Le chapitre sur les collections non modifiables plus loin dans cette partie couvre quand choisir quoi.

Exemple pratique : déduplication, algèbre des ensembles et ordre

Le programme ci-dessous utilise les quatre implémentations, démontre les opérations en masse sur des données réelles, et montre comment l'ordre d'itération diffère entre HashSet, LinkedHashSet et TreeSet.

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

• add a retourné false pour chaque \"java\" en doublon — c'est ainsi qu'on écrit un dédupliqueur en deux lignes.
• L'union, l'intersection et la différence nécessitent chacune un seul addAll/retainAll/removeAll — copiez d'abord si vous ne voulez pas perdre l'original.
• Les trois implémentations contiennent les mêmes éléments et se comparent comme égales, mais itèrent dans des ordres très différents. Choisissez l'implémentation selon l'ordre dont vous avez besoin, pas par réflexe.

La suite

L'implémentation de Set la plus courante — celle vers laquelle vous vous tournez sauf raison contraire — est basée sur une table de hachage. HashSet est la prochaine étape ; nous couvrirons le facteur de charge, le rehachage et ce que signifie « temps quasi-constant » en pratique.

Pratique