HashSet en Java - java.util.HashSet

HashSet — Ensembles basés sur le hachage

  Prérequis

Maîtriser les concepts de collections Java. Comprendre le fonctionnement des tables de hachage. Connaître les méthodes hashCode() et equals(). Avoir des notions sur les listes chaînées et les arbres binaires.

  Objectifs

Comprendre le fonctionnement d'un HashSet et son implémentation basée sur les tables de hachage. Savoir utiliser les opérations d'ajout, suppression, recherche et parcours. Maîtriser les constructeurs et les méthodes spécifiques. Connaître l'optimisation par arbres binaires (Java 8+).

1. Pourquoi utiliser un Set ?

Les listes (ArrayList, LinkedList) vous permettent de contrôler l'ordre des éléments, mais la recherche d'un élément nécessite de parcourir toute la collection (complexité O(n)). Si vous ne vous souciez pas de l'ordre, des structures comme HashSet offrent des recherches beaucoup plus rapides (complexité O(1) en moyenne).

2. Principe de la table de hachage

En Java, les tables de hachage sont implémentées comme un tableau de listes chaînées (ou d'arbres binaires depuis Java 8).

3. Constructeurs de HashSet

4. Méthodes principales

5. Exemples d'utilisation

  Exemple 1 — Opérations de base sur un HashSet

import java.util.HashSet;
import java.util.Iterator;

public class TestHashSet {
    public static void main(String[] args) {
        HashSet<String> pays = new HashSet<>();

        // Ajout d'éléments
        pays.add("Maroc");
        pays.add("Tunisie");
        pays.add("Algérie");
        pays.add("Espagne");
        pays.add("Malaisie");
        pays.add("Espagne");  // Tentative d'ajout en double → ignoré

        // Affichage (l'ordre n'est pas garanti)
        System.out.println("HashSet : " + pays);

        // Vérification d'appartenance
        System.out.println("Contient Tunisie ? " + pays.contains("Tunisie"));

        // Suppression
        pays.remove("Espagne");
        System.out.println("Après suppression : " + pays);

        // Parcours avec Iterator
        System.out.println("\n--- Parcours avec Iterator ---");
        Iterator<String> it = pays.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

HashSet : [Tunisie, Malaisie, Algérie, Maroc, Espagne]
Contient Tunisie ? true
Après suppression : [Tunisie, Malaisie, Algérie, Maroc]

--- Parcours avec Iterator ---
Tunisie
Malaisie
Algérie
Maroc

  Exemple 2 — HashSet à partir d'une autre collection

import java.util.HashSet;
import java.util.ArrayList;

public class TestHashSetFromCollection {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("Maroc");
        list.add("Tunisie");
        list.add("Algérie");

        // Création d'un HashSet à partir de l'ArrayList
        HashSet<String> set = new HashSet<>(list);
        set.add("France");

        System.out.println("HashSet créé depuis ArrayList : " + set);
    }
}

HashSet créé depuis ArrayList : [Tunisie, Algérie, Maroc, France]

6. Parcours d'un HashSet

  Exemple 3 — Différentes façons de parcourir

import java.util.HashSet;

public class ParcoursHashSet {
    public static void main(String[] args) {
        HashSet<String> fruits = new HashSet<>();
        fruits.add("Pomme");
        fruits.add("Banane");
        fruits.add("Orange");
        fruits.add("Mangue");

        // 1. Boucle for-each (recommandée)
        System.out.println("=== for-each ===");
        for (String fruit : fruits) {
            System.out.println(fruit);
        }

        // 2. Avec Iterator
        System.out.println("\n=== Iterator ===");
        var iterator = fruits.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

        // 3. Avec forEach() + lambda (Java 8+)
        System.out.println("\n=== forEach() lambda ===");
        fruits.forEach(fruit -> System.out.println(fruit));

        // 4. Avec Stream (Java 8+)
        System.out.println("\n=== Stream ===");
        fruits.stream().sorted().forEach(System.out::println);
    }
}

=== for-each ===
Pomme
Banane
Orange
Mangue

=== Iterator ===
Pomme
Banane
Orange
Mangue

=== forEach() lambda ===
Pomme
Banane
Orange
Mangue

=== Stream ===
Banane
Mangue
Orange
Pomme

7. HashSet avec objets personnalisés

  Exemple 4 — HashSet d'étudiants

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

class Etudiant {
    private int id;
    private String nom;
    private String prenom;

    public Etudiant(int id, String nom, String prenom) {
        this.id = id;
        this.nom = nom;
        this.prenom = prenom;
    }

    // Getters...

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Etudiant etudiant = (Etudiant) o;
        return id == etudiant.id &&
               Objects.equals(nom, etudiant.nom) &&
               Objects.equals(prenom, etudiant.prenom);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, nom, prenom);
    }

    @Override
    public String toString() {
        return String.format("%s %s (id: %d)", prenom, nom, id);
    }
}

public class TestHashSetObjets {
    public static void main(String[] args) {
        HashSet<Etudiant> etudiants = new HashSet<>();

        etudiants.add(new Etudiant(1, "ESSADDOUKI", "Mostafa"));
        etudiants.add(new Etudiant(2, "KAYOUH", "Mohamed"));
        etudiants.add(new Etudiant(1, "ESSADDOUKI", "Mostafa"));  // Doublon → ignoré

        System.out.println("Nombre d'étudiants : " + etudiants.size());
        System.out.println(etudiants);
    }
}

Nombre d'étudiants : 2
[Mostafa ESSADDOUKI (id: 1), Mohamed KAYOUH (id: 2)]

8. LinkedHashSet — HashSet avec ordre d'insertion

  Exemple 5 — LinkedHashSet vs HashSet

import java.util.HashSet;
import java.util.LinkedHashSet;

public class CompareHashSetLinkedHashSet {
    public static void main(String[] args) {
        // HashSet → ordre non garanti
        HashSet<String> hashSet = new HashSet<>();
        hashSet.add("Z");
        hashSet.add("A");
        hashSet.add("M");
        hashSet.add("B");
        System.out.println("HashSet : " + hashSet);

        // LinkedHashSet → ordre d'insertion
        LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add("Z");
        linkedHashSet.add("A");
        linkedHashSet.add("M");
        linkedHashSet.add("B");
        System.out.println("LinkedHashSet : " + linkedHashSet);
    }
}

HashSet : [A, B, Z, M]
LinkedHashSet : [Z, A, M, B]

9. TreeSet — Ensemble trié

10. Exemple complet — Gestion d'une liste de contacts unique

  Exemple 6 — Annuaire sans doublons

import java.util.HashSet;
import java.util.Scanner;

class Contact {
    private String nom;
    private String telephone;

    public Contact(String nom, String telephone) {
        this.nom = nom;
        this.telephone = telephone;
    }

    public String getNom() { return nom; }
    public String getTelephone() { return telephone; }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Contact contact = (Contact) o;
        return nom.equalsIgnoreCase(contact.nom) ||
               telephone.equals(contact.telephone);
    }

    @Override
    public int hashCode() {
        return Objects.hash(nom.toLowerCase(), telephone);
    }

    @Override
    public String toString() {
        return String.format("%s → %s", nom, telephone);
    }
}

public class AnnuaireSansDoublons {
    private HashSet<Contact> contacts;

    public AnnuaireSansDoublons() {
        contacts = new HashSet<>();
    }

    public boolean ajouterContact(String nom, String telephone) {
        Contact nouveau = new Contact(nom, telephone);
        if (contacts.add(nouveau)) {
            System.out.println("Contact ajouté : " + nouveau);
            return true;
        } else {
            System.out.println("Contact déjà existant (nom ou téléphone identique)");
            return false;
        }
    }

    public boolean supprimerContact(String nom) {
        Contact recherche = new Contact(nom, "");
        if (contacts.remove(recherche)) {
            System.out.println("Contact supprimé : " + nom);
            return true;
        } else {
            System.out.println("Contact non trouvé : " + nom);
            return false;
        }
    }

    public boolean rechercherContact(String nom) {
        for (Contact c : contacts) {
            if (c.getNom().equalsIgnoreCase(nom)) {
                System.out.println("Trouvé : " + c);
                return true;
            }
        }
        System.out.println("Contact non trouvé : " + nom);
        return false;
    }

    public void afficherTous() {
        if (contacts.isEmpty()) {
            System.out.println("Annuaire vide.");
            return;
        }
        System.out.println("\n=== ANNUAIRE (" + contacts.size() + " contact(s)) ===");
        for (Contact c : contacts) {
            System.out.println("  " + c);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        AnnuaireSansDoublons annuaire = new AnnuaireSansDoublons();
        Scanner scanner = new Scanner(System.in);
        int choix;

        do {
            System.out.println("\n╔════════════════════════════════════╗");
            System.out.println("║     ANNUAIRE SANS DOUBLONS         ║");
            System.out.println("╠════════════════════════════════════╣");
            System.out.println("║ 1. Ajouter un contact              ║");
            System.out.println("║ 2. Supprimer un contact            ║");
            System.out.println("║ 3. Rechercher un contact           ║");
            System.out.println("║ 4. Afficher tous les contacts      ║");
            System.out.println("║ 5. Quitter                         ║");
            System.out.println("╚════════════════════════════════════╝");
            System.out.print("Votre choix : ");
            choix = scanner.nextInt();
            scanner.nextLine();

            switch (choix) {
                case 1:
                    System.out.print("Nom : ");
                    String nom = scanner.nextLine();
                    System.out.print("Téléphone : ");
                    String tel = scanner.nextLine();
                    annuaire.ajouterContact(nom, tel);
                    break;
                case 2:
                    System.out.print("Nom : ");
                    nom = scanner.nextLine();
                    annuaire.supprimerContact(nom);
                    break;
                case 3:
                    System.out.print("Nom : ");
                    nom = scanner.nextLine();
                    annuaire.rechercherContact(nom);
                    break;
                case 4:
                    annuaire.afficherTous();
                    break;
                case 5:
                    System.out.println("Au revoir !");
                    break;
                default:
                    System.out.println("Choix invalide !");
            }
        } while (choix != 5);

        scanner.close();
    }
}

11. Exercice

import java.util.HashSet;
import java.util.Scanner;

public class DetecteurDoublons {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("Entrez une liste de mots séparés par des espaces :");
        String ligne = scanner.nextLine();

        // Nettoyage et découpage
        String[] mots = ligne.toLowerCase().split("\\s+");

        HashSet<String> motsUniques = new HashSet<>();
        HashSet<String> motsDoublons = new HashSet<>();

        // Détection des doublons
        for (String mot : mots) {
            if (!motsUniques.add(mot)) {
                // Si add() retourne false, l'élément existe déjà
                motsDoublons.add(mot);
            }
        }

        // Affichage des résultats
        System.out.println("\n=== RÉSULTATS ===");
        System.out.println("Nombre total de mots : " + mots.length);
        System.out.println("Nombre de mots uniques : " + motsUniques.size());

        System.out.println("\n--- Mots sans doublons ---");
        for (String mot : motsUniques) {
            System.out.print(mot + " ");
        }

        if (!motsDoublons.isEmpty()) {
            System.out.println("\n\n--- Mots en double ---");
            for (String mot : motsDoublons) {
                System.out.print(mot + " ");
            }
        } else {
            System.out.println("\n\nAucun doublon détecté !");
        }

        scanner.close();
    }
}

Entrez une liste de mots séparés par des espaces :
le chat et le chien jouent et le chat dort

=== RÉSULTATS ===
Nombre total de mots : 11
Nombre de mots uniques : 7

--- Mots sans doublons ---
chat et jouent chien le dort

--- Mots en double ---
chat le et

  L'essentiel en bref