Java HashSet

HashSet<E> est l'implémentation vers laquelle on se tourne en premier lorsqu'on veut un ensemble. Elle repose sur une table de hachage — en interne, c'est un HashMap avec une valeur fictive — donc add, remove et contains sont en O(1) attendu : le coût se résume à un hachage de l'élément plus une ou deux vérifications d'égalité, quel que soit le nombre d'éléments déjà présents dans l'ensemble. C'est cette propriété qui fait des ensembles de hachage la bonne réponse aux questions du type « ai-je déjà vu ça ? », aux passes de déduplication et à tout contrôle d'appartenance qui serait quadratique avec une List.

Ce que « temps quasi-constant » signifie réellement

Le temps constant n'est pas gratuit ; il est amorti. Chaque opération fait à peu près ceci :

1. Calculer e.hashCode(). Mélanger les bits hauts et bas afin qu'un hash comme 0x...0000 ne s'effondre pas dans le bucket 0.
2. Chercher le bucket à bucketIndex = hash & (table.length - 1).
3. Parcourir la chaîne liée du bucket (ou, depuis Java 8, un petit arbre équilibré si la chaîne est devenue longue) en appelant equals jusqu'à trouver l'élément ou atteindre la fin.

L'étape 3 est là où le coût dérapé si votre hashCode est mauvais. Avec un hash raisonnable, la chaîne comporte un ou deux éléments ; avec un hash constant, elle contient tous les éléments jamais insérés. C'est la différence entre O(1) et O(n) par opération.

Capacité, facteur de charge et le rehachage

Un HashSet possède un tableau de buckets en arrière-plan. Deux paramètres du constructeur le contrôlent :

• Capacité initiale — le nombre de buckets de départ. Par défaut : 16. Arrondi à la puissance de deux supérieure.
• Facteur de charge — le ratio éléments/buckets à partir duquel la table double de taille. Par défaut : 0.75.

Lorsque size / capacity dépasse le facteur de charge, l'ensemble se rehache : il alloue un nouveau tableau deux fois plus grand et redistribue chaque élément. Un rehachage est O(n) — c'est le coût qui s'amortit sur les insertions O(1) qui le précèdent. Pré-dimensionner un ensemble dont on sait qu'il contiendra environ 1 000 000 d'éléments évite une vingtaine de doublements :

Set<Long> ids = new HashSet<>(1_500_000); // skip the doublings up to ~1M

Des facteurs de charge plus petits (p. ex. 0.5) gaspillent de la mémoire mais réduisent les collisions ; des valeurs plus grandes (p. ex. 0.9) sont plus compactes mais allongent les chaînes. Le 0.75 par défaut est un équilibre calibré par Sun il y a des décennies et qui tient toujours — ne le modifiez pas sans un benchmark.

Null, ordre d'itération, sécurité des threads

Trois règles :

1. Un élément null est autorisé. HashSet le stocke dans le bucket 0 avec un hash spécial de 0. C'est une commodité délibérée — Map.of/Set.of et TreeSet interdisent tous les deux null.
2. Aucun ordre d'itération n'est garanti. L'ordre change lors du rehachage de la table et n'est même pas cohérent entre les JVM. Si vous avez besoin de l'ordre d'insertion, utilisez LinkedHashSet ; si vous avez besoin d'un ordre trié, utilisez TreeSet.
3. Non thread-safe. Une mutation concurrente corrompra la structure. Pour du code multi-threadé, utilisez ConcurrentHashMap.newKeySet() (une vue Set d'une map concurrente) ou enveloppez dans Collections.synchronizedSet.

hashCode est votre responsabilité

Placer votre propre classe dans un HashSet ne fonctionne que si vous surchargez hashCode et equals de manière cohérente. Le contrat issu de Object :

• Si a.equals(b), alors a.hashCode() == b.hashCode().
• Si a.hashCode() == b.hashCode(), a.equals(b) peut quand même être faux (une collision).

Violer la première partie du contrat est la source la plus fréquente du bug « je l'ai ajouté, mais contains retourne false ». Les IDE modernes et le mot-clé record génèrent les deux méthodes pour vous — utilisez-les.

record Tag(String name) {}            // hashCode/equals auto-generated
Set<Tag> tags = new HashSet<>();
tags.add(new Tag("java"));
System.out.println(tags.contains(new Tag("java"))); // true

Le piège des éléments mutables

Un bug plus subtil : stocker un objet dont le hashCode dépend de champs mutables, puis le muter après l'insertion. Le hash qui a déterminé dans quel bucket l'élément réside a été calculé au moment de l'insertion ; une fois qu'on modifie un champ dont dépend le hash, l'objet se trouve dans le « mauvais » bucket et contains parcourt une chaîne qui ne l'inclut pas — même si c'est exactement la même référence.

class Box {
    int n;
    Box(int n) { this.n = n; }
    @Override public boolean equals(Object o) {
        return o instanceof Box b && b.n == n;
    }
    @Override public int hashCode() { return Integer.hashCode(n); }
}

Box box = new Box(1);
Set<Box> set = new HashSet<>();
set.add(box);
box.n = 2;                  // mutate a field hashCode depends on
System.out.println(set.contains(box)); // false — element is now in the wrong bucket

Notez que ce problème n'apparaît que lorsque hashCode lit un état mutable. StringBuilder, par exemple, utilise le hachage d'identité, de sorte que le muter ne le déplace jamais entre les buckets — mais s'y fier est fragile. La solution n'est pas d'être astucieux ; c'est de placer des éléments immuables dans les ensembles de hachage. String, Integer, vos propres records, des DTO fraîchement capturés. Si vous avez besoin d'un ensemble indexé par un état mutable, indexez par une projection immuable de celui-ci.

Un exemple concret : déduplication, appartenance et capacité

Le programme ci-dessous illustre les quatre raisons pour lesquelles on utilise un HashSet : la déduplication, les tests d'appartenance rapides, l'algèbre des ensembles et le coût d'un mauvais hashCode.

Ce qu'il faut retenir :

• La boucle de déduplication est O(n) — chaque add est en temps constant, et le unique.size() final correspond au nombre d'entrées distinctes.
• Un contains dans un ensemble de 1 000 000 d'éléments a retourné en microsecondes. C'est la propriété qui fait de HashSet l'outil de test d'appartenance du JDK.
• Le record Tag obtient equals/hashCode gratuitement, donc deux objets Tag("java") se réduisent à un seul élément.
• L'exemple Box illustre le piège : le même objet, muté après l'insertion de sorte que son hashCode a changé, rapporte maintenant contains(box) == false. Mettez des éléments immuables dans les ensembles de hachage.

La suite

HashSet ne garantit aucun ordre d'itération. Si vous avez besoin de mémoriser l'ordre dans lequel vous avez inséré des éléments — par exemple si vous construisez une liste de tags et que l'utilisateur s'attend à les voir dans l'ordre où ils ont été ajoutés — le bon outil est LinkedHashSet. C'est le chapitre suivant.

Pratique