Notes S13

Mise en œuvre des collections : ensembles (CS-108)

1. Introduction

La bibliothèque Java offre deux mises en œuvre des ensembles :

HashSet : basée sur les tables de hachage → opérations principales en O(1)
TreeSet : basée sur les arbres binaires de recherche → opérations principales en O(log n)

Les mêmes techniques sont utilisées par HashMap et TreeMap pour les tables associatives. La mise en œuvre par table de hachage étant la plus simple et la plus efficace, c’est le sujet de la leçon.

2. Interface SSet

Version simplifiée de l’interface des ensembles :

public interface SSet<E> extends Iterable<E> {
    int size();
    boolean isEmpty();
    void add(E e);
    void remove(E e);
    boolean contains(E e);
    Iterator<E> iterator();
}

Trois classes l’implémentent :

SAbstractSet (héritable) : mises en œuvre par défaut (isEmpty à partir de size, etc.)
SListSet (instanciable) : ensemble basé sur une liste — inefficace mais pédagogique
SHashSet (instanciable) : ensemble basé sur une table de hachage

Aucune ne redéfinit equals ou hashCode : l’égalité par référence convient pour ces classes non immuables.

3. SAbstractSet — Ensemble abstrait

Fournit deux méthodes utiles à toutes les sous-classes :

public abstract class SAbstractSet<E> implements SSet<E> {
    @Override
    public boolean isEmpty() {
        return size() == 0;
    }
 
    @Override
    public String toString() {
        StringJoiner j = new StringJoiner(", ", "{", "}");
        for (E e : this)
            j.add(e.toString());
        return j.toString();
    }
}

isEmpty pourrait être une méthode par défaut dans SSet, mais pas toString : Java interdit les méthodes par défaut qui redéfinissent des méthodes de Object.

4. Ensemble par liste (SListSet)

Utilise une liste chaînée sans doublons. Toutes les opérations principales (add, remove, contains) sont en O(n) → la bibliothèque Java ne fournit pas d’équivalent. C’est utile uniquement pour comprendre la version hash table.

public final class SListSet<E> extends SAbstractSet<E> {
    private final SList<E> list = new SLinkedList<>();
 
    @Override
    public int size() {
        return list.size();
    }
    // ... autres méthodes ci-dessous
}

4.1 Ajout

Pour éviter les doublons, on n’ajoute que si l’élément n’est pas déjà présent → complexité O(n) (alors que l’ajout dans une liste peut être O(1)). L’ajout se fait en tête, car c’est très rapide dans une liste chaînée.

@Override
public void add(E e) {
    if (! list.contains(e))
        list.add(0, e);
}

4.2 Suppression

On parcourt avec un itérateur jusqu’à trouver l’élément, puis on s’arrête (pas de doublons).

@Override
public void remove(E e) {
    Iterator<E> listIt = list.iterator();
    while (listIt.hasNext()) {
        E e1 = listIt.next();
        if (e1.equals(e)) {
            listIt.remove();
            return;
        }
    }
}

4.3 Test d’appartenance

Trivial grâce à contains de l’interface SList :

@Override
public boolean contains(E e) {
    return list.contains(e);
}

4.4 Itération

On retourne directement l’itérateur de la liste sous-jacente :

@Override
public Iterator<E> iterator() {
    return list.iterator();
}

5. Ensemble par table de hachage (SHashSet)

Idée centrale

Plutôt que une seule liste de longueur n, on stocke les éléments dans environ n listes de longueur environ 1, placées dans un tableau. Si on sait déterminer rapidement (en O(1)) à quelle liste un élément appartient → opérations en O(1).

Ce moyen, c’est le hachage : l’index de la liste est obtenu en ramenant la valeur de hachage de l’élément à un index valide du tableau.

Structure de la classe

public final class SHashSet<E> extends SAbstractSet<E> {
    private int size = 0;
    private SList<E>[] table = newTable(10);
 
    @Override
    public int size() {
        return size;
    }
 
    // ... autres méthodes ci-dessous
 
    private static <E> SList<E>[] newTable(int capacity) {
        @SuppressWarnings("unchecked")
        SList<E>[] table = new SList[capacity];
        for (int i = 0; i < capacity; ++i)
            table[i] = new SLinkedList<>();
        return table;
    }
}

Vocabulaire :

Capacité (capacity) = table.length
Facteur de charge (load factor) = size / capacity, idéalement proche de 1

5.1 Indexation

On ramène la valeur de hachage à un index valide par le reste de la division entière par la capacité. Attention : hashCode peut renvoyer un entier négatif, et l’opérateur % retourne une valeur du signe du dividende → on utilise Math.floorMod, qui retourne une valeur du signe du diviseur.

private static <E> SList<E> listFor(SList<E>[] table, E elem) {
    return table[Math.floorMod(elem.hashCode(), table.length)];
}

Cette méthode est statique et prend la table en paramètre (et non l’attribut), car cela sera utile pour le rehachage plus bas.

5.2 Ajout

Deux phases :

Obtenir la liste correspondant à l’élément (listFor)
Ajouter à cette liste s’il n’y est pas déjà (identique à SListSet)

@Override
public void add(E e) {
    SList<E> list = listFor(table, e);
    if (! list.contains(e)) {
        list.add(0, e);
        size += 1;
    }
}

C’est ici qu’on voit pourquoi hashCode et equals doivent être compatibles : la phase 1 utilise hashCode pour trouver la liste, la phase 2 utilise equals pour vérifier l’appartenance.

5.3 Suppression

Mêmes deux phases :

@Override
public void remove(E e) {
    Iterator<E> listIt = listFor(table, e).iterator();
    while (listIt.hasNext()) {
        E e1 = listIt.next();
        if (e1.equals(e)) {
            listIt.remove();
            size -= 1;
            return;
        }
    }
}

5.4 Test d’appartenance

Deux phases également :

@Override
public boolean contains(E e) {
    return listFor(table, e).contains(e);
}

5.5 Itération

Le parcours est bidimensionnel (un tableau de listes). L’itérateur a trois attributs :

listIndex : index de la liste en cours
listIt : itérateur sur cette liste
remaining : compteur du nombre d’éléments restants (sert pour hasNext)

@Override
public Iterator<E> iterator() {
    return new Iterator<E>() {
        int remaining = size;
        int listIndex = 0;
        Iterator<E> listIt = table[listIndex].iterator();
 
        @Override
        public boolean hasNext() {
            return remaining > 0;
        }
 
        @Override
        public E next() {
            if (! hasNext())
                throw new NoSuchElementException();
            remaining -= 1;
            while (! listIt.hasNext()) {
                listIndex += 1;
                listIt = table[listIndex].iterator();
            }
            return listIt.next();
        }
 
        @Override
        public void remove() {
            listIt.remove();
            size -= 1;
        }
    };
}

L’ordre de parcours est quelconque : il dépend de l’ordre d’ajout et de la capacité de la table.

5.6 Rehachage

Avec une capacité fixe à 10, on perd le O(1) dès que size grandit : il faut redimensionner la table pour garder une capacité proche de la taille.

On tolère une variation du facteur de charge dans un intervalle acceptable pour éviter de redimensionner trop souvent :

private static int MIN_CAPACITY = 10;
private static double MIN_LOAD_FACTOR = 0.4;
private static double MAX_LOAD_FACTOR = 1;
private static double IDEAL_LOAD_FACTOR = 0.7;

Algorithme du rehachage : si le facteur de charge sort de [0.4, 1], on crée une nouvelle table dont la capacité donne un facteur de charge idéal de 0.7, on y recopie tous les éléments, et on remplace l’ancienne.

private void rehashIfNeeded() {
    double loadFactor = size / (double) table.length;
    if (MIN_LOAD_FACTOR < loadFactor
        && loadFactor < MAX_LOAD_FACTOR)
        return;
    int idealCapacity = (int) (size / IDEAL_LOAD_FACTOR);
    if (idealCapacity < MIN_CAPACITY)
        return;
    SList<E>[] newTable = newTable(idealCapacity);
    for (E e : this)
        listFor(newTable, e).add(0, e);
    table = newTable;
}

C’est ici qu’on voit pourquoi listFor est statique et prend la table en paramètre : pendant le rehachage, on utilise la nouvelle table (newTable), pas encore affectée à l’attribut.

Où l’appeler ? À chaque mise à jour de size, donc dans add et remove :

@Override
public void add(E e) {
    SList<E> list = listFor(table, e);
    if (! list.contains(e)) {
        list.add(0, e);
        size += 1;
        rehashIfNeeded();
    }
}
 
@Override
public void remove(E e) {
    Iterator<E> listIt = listFor(table, e).iterator();
    while (listIt.hasNext()) {
        E e1 = listIt.next();
        if (e1.equals(e)) {
            listIt.remove();
            size -= 1;
            rehashIfNeeded();
            return;
        }
    }
}

PAS dans la méthode remove de l’itérateur : rehacher pendant un parcours casserait la position des éléments en cours d’itération.

Points clés à retenir

Hash table = tableau de listes + fonction de hachage
Compatibilité obligatoire entre hashCode et equals (sinon add/contains peuvent diverger)
Utiliser Math.floorMod plutôt que % à cause des hashCode négatifs
Le rehachage maintient le facteur de charge dans [0.4, 1], cible 0.7
Pas de rehachage pendant une itération
Si la fonction de hachage est en O(1) et répartit bien, toutes les opérations principales sont en O(1)

Quartz 4

Explorer

Notes S13

Notes S13

Mise en œuvre des collections : ensembles (CS-108)

1. Introduction

2. Interface SSet

3. SAbstractSet — Ensemble abstrait

4. Ensemble par liste (SListSet)

4.1 Ajout

4.2 Suppression

4.3 Test d’appartenance

4.4 Itération

5. Ensemble par table de hachage (SHashSet)

Idée centrale

Structure de la classe

5.1 Indexation

5.2 Ajout

5.3 Suppression

5.4 Test d’appartenance

5.5 Itération

5.6 Rehachage

Points clés à retenir

Graph View

Table of Contents