Java HashSet : valeurs uniques, appartenance et opérations sur les ensembles

Un ensemble stocke des valeurs uniques

Un HashSet (de java.util) est une collection qui conserve chaque valeur au plus une fois. Il n'y a pas de clés ni de valeurs associées comme dans un HashMap - juste un sac d'éléments distincts. Son seul rôle est de répondre vite à une question : « est-ce que cette chose est là-dedans ? »

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<String> tags = new HashSet<>();
        tags.add("java");
        tags.add("backend");
        tags.add("java");   // doublon - ignoré

        System.out.println(tags.contains("java"));     // true
        System.out.println(tags.contains("frontend")); // false
        System.out.println(tags.size());               // 2
    }
}

Il y a un seul paramètre de type, <ElementType>. Comme avec ArrayList et HashMap, on type généralement la variable avec l'interface Set et on construit un HashSet.

add renvoie si la valeur était nouvelle

add ne se contente pas de stocker la valeur : il renvoie un boolean qui indique si l'ensemble a réellement changé. Ajouter une valeur déjà présente renvoie false et laisse l'ensemble intact.

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<Integer> seen = new HashSet<>();

        System.out.println(seen.add(7));  // true  - 7 était nouveau
        System.out.println(seen.add(7));  // false - déjà présent
        System.out.println(seen);
    }
}

Cette valeur de retour est vraiment utile : if (!seen.add(x)) { /* x est un doublon */ } vous permet de détecter les doublons en une seule ligne au fil de l'eau.

Supprimer les doublons d'une liste

Comme un ensemble refuse les répétitions, le moyen le plus rapide de dédupliquer une collection est de la verser dedans. Le constructeur de HashSet accepte n'importe quelle autre collection :

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>(List.of("Ada", "Boris", "Ada", "Chen", "Boris"));

        Set<String> unique = new HashSet<>(names);
        System.out.println(unique);          // chaque nom une fois
        System.out.println(unique.size());   // 3

        // besoin de récupérer une List ?
        List<String> deduped = new ArrayList<>(unique);
        System.out.println(deduped.size());  // 3
    }
}

C'est la raison la plus fréquente pour laquelle les débutants se tournent vers un ensemble. Sachez simplement que vous perdez l'ordre d'origine lors de l'aller-retour - utilisez LinkedHashSet si l'ordre compte (abordé plus bas).

contains, remove et size

Les opérations courantes reprennent celles des autres collections :

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<String> tags = new HashSet<>();
        tags.add("java");
        tags.add("backend");
        tags.add("api");

        System.out.println(tags.contains("api"));  // true
        System.out.println(tags.size());           // 3

        tags.remove("backend");
        System.out.println(tags.contains("backend")); // false

        tags.clear();
        System.out.println(tags.isEmpty());         // true
    }
}

Le grand avantage par rapport à un ArrayList, c'est contains. Une liste doit parcourir chaque élément pour y répondre (O(n)) ; un HashSet saute presque directement à la réponse (à peu près O(1)). Quand vous vous surprenez à appeler list.contains(...) à l'intérieur d'une boucle, c'est généralement le signal qu'il faut passer à un ensemble.

Opérations sur les ensembles : union, intersection, différence

Les ensembles brillent quand on les combine. Les méthodes se lisent presque comme du langage courant une fois qu'on sait laquelle est laquelle :

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<Integer> a = new HashSet<>(Set.of(1, 2, 3, 4));
        Set<Integer> b = new HashSet<>(Set.of(3, 4, 5, 6));

        Set<Integer> union = new HashSet<>(a);
        union.addAll(b);            // tout ce qui est dans l'un ou l'autre
        System.out.println(union);  // 1 2 3 4 5 6

        Set<Integer> intersection = new HashSet<>(a);
        intersection.retainAll(b);  // seulement ce qui est dans les deux
        System.out.println(intersection); // 3 4

        Set<Integer> difference = new HashSet<>(a);
        difference.removeAll(b);    // dans a mais pas dans b
        System.out.println(difference);   // 1 2
    }
}

Le piège essentiel : addAll, retainAll et removeAll modifient l'ensemble sur lequel ils sont appelés. C'est pourquoi chaque exemple copie d'abord a dans un HashSet tout neuf - sinon vous détruiriez votre original. Construisez un nouvel ensemble pour chaque résultat.

HashSet ne conserve pas l'ordre

Comme HashMap, un HashSet ne garantit aucun ordre d'itération, et l'ordre peut varier d'une exécution à l'autre. Si vous avez besoin de prévisibilité :

• LinkedHashSet préserve l'ordre d'insertion - l'ordre dans lequel vous avez ajouté les éléments.
• TreeSet garde les éléments triés selon leur ordre naturel (ou un Comparator que vous fournissez).

import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Set<String> insertion = new LinkedHashSet<>();
        insertion.add("gamma");
        insertion.add("alpha");
        insertion.add("beta");
        System.out.println(insertion);  // [gamma, alpha, beta]

        Set<String> sorted = new TreeSet<>(insertion);
        System.out.println(sorted);      // [alpha, beta, gamma]
    }
}

Les trois implémentent l'interface Set, donc passer de l'un à l'autre se résume à une modification d'une seule ligne dans le constructeur.

Les éléments doivent être hachables

Un HashSet repose en coulisses sur un HashMap, donc la même règle s'applique : il localise les éléments en les hachant, ce qui signifie que les méthodes hashCode() et equals() d'un élément doivent être cohérentes. Les types intégrés comme String et Integer font déjà cela correctement, c'est pourquoi les chaînes "java" en double fusionnent correctement plus haut. Si vous stockez des instances de votre propre classe, redéfinissez à la fois equals et hashCode - sinon deux objets « égaux » par leur sens seront traités comme distincts, et contains ainsi que la déduplication échoueront silencieusement.

Suite : Parcourir les collections

Vous avez désormais rencontré les trois collections incontournables - ArrayList, HashMap et HashSet. Chacune se parcourt un peu différemment, et il y a des pièges subtils (comme modifier une collection pendant qu'on boucle dessus). Ensuite, nous allons tout rassembler et voir comment parcourir proprement les collections avec la boucle for-each, les itérateurs et forEach.