HashSet

1. Unicité des éléments Un HashSet ne peut pas contenir de doublons. Lorsque vous essayez d'ajouter un élément déjà présent, l'ajout est simplement ignoré. C'est très utile pour éliminer rapidement les doublons d'une collection.

2. Non-ordonné Contrairement à une liste, un HashSet ne maintient pas l'ordre des éléments. Les éléments sont stockés en fonction de leur valeur de hachage, ce qui permet des opérations très rapides.

3. Performances Les opérations de base comme l'ajout, la suppression et la recherche sont très efficaces, avec une complexité de temps O(1) en moyenne.

4. Utilisations courantes

• Élimination des doublons
• Vérification rapide de présence d'un élément
• Opérations ensemblistes (union, intersection)

Quelques points importants à retenir :

• Un HashSet utilise la méthode hashCode() et equals() pour identifier les éléments uniques
• Il est particulièrement efficace pour les grandes collections où vous avez besoin de vérifications rapides
• Il est moins adapté si vous avez besoin de maintenir un ordre spécifique (dans ce cas, utilisez un TreeSet)

Comment fonctionne le hashCode()?

Lorsque deux objets ont le même hashCode(), on parle de "collision de hachage". Voici comment Java gère ces situations dans un HashSet :

1. Processus de vérification Quand vous ajoutez un élément à un HashSet, deux étapes sont nécessaires :

• Calculer le code de hachage (méthode hashCode())
• Vérifier l'égalité (méthode equals())

2. Exemple détaillé

import java.util.HashSet;
import java.util.Objects;

class Personne {
    private String nom;
    private int age;

    public Personne(String nom, int age) {
        this.nom = nom;
        this.age = age;
    }

    // Volontairement mauvaise implémentation de hashCode()
    @Override
    public int hashCode() {
        return 42; // Tous les objets auront le même code de hachage
    }

    // Implémentation correcte de equals()
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Personne personne = (Personne) o;
        return age == personne.age && 
               Objects.equals(nom, personne.nom);
    }

    @Override
    public String toString() {
        return nom + " (" + age + " ans)";
    }
}

public class CollisionHashSet {
    public static void main(String[] args) {
        HashSet<Personne> personnes = new HashSet<>();

        Personne alice1 = new Personne("Alice", 30);
        Personne alice2 = new Personne("Alice", 30);
        Personne bob = new Personne("Bob", 25);

        personnes.add(alice1);
        personnes.add(alice2);
        personnes.add(bob);

        System.out.println("Nombre de personnes : " + personnes.size());
        System.out.println("Personnes dans le HashSet : " + personnes);
    }
}

Mécanisme interne Quand vous ajoutez un élément, Java fait :

1. Calcule le hashCode()
2. Si le code de hachage est différent → Élément distinct
3. Si le code de hachage est identique :
   • Compare avec equals()
   • Si equals() retourne false → Élément distinct
   • Si equals() retourne true → Considéré comme doublon

Résultat de l'exemple

• alice1 et alice2 ont le même hashCode() (collision), Java appelle equals() qui confirme qu'ils sont identiques → doublon ignoré
• bob a aussi le même hashCode() (42), mais equals() retourne false → élément distinct, donc ajouté
• Le HashSet contiendra 2 éléments

Conséquences des collisions

• Trop de collisions dégrade les performances
• Transforme la recherche de O(1) à O(n)
• La structure interne (table de hachage) s'adapte

Meilleure pratique

• Implémenter hashCode() et equals() de manière cohérente
• Distribuer uniformément les codes de hachage
• Utiliser Objects.hash() pour des implémentations simples