Série 6 – Ensembles par hachage : corrigé

Pour parcourir les deux dimensions de la table de hachage, l'itérateur doit logiquement stocker une information par dimension, comme expliqué dans l'énoncé.

La position dans la première dimension est stockée dans un entier nommé i, initialisé à 0. La position dans la seconde dimension est quant-à-elle stockée sous la forme d'un itérateur nommé it et initialisé avec un itérateur sur la première liste, c-à-d celle qui apparaît à la position 0 dans la table.

Ces deux informations sont liées par l'invariant suivant : l'itérateur it est toujours un itérateur sur la liste de position i dans la table de hachage.

La méthode next de l'itérateur commence par appeler la méthode hasNext de l'itérateur it afin de savoir s'il reste des éléments dans la liste d'indice i. Tant que ce n'est pas le cas, elle passe à la liste suivante en incrémentant i et en obtenant un itérateur sur la liste d'après.

Une fois cela fait, il est garanti que l'itérateur it possède encore un élément. Celui-ci est obtenu avec la méthode next de it et directement retourné.

Si la compréhension de cette technique d'itération vous pose problème, pensez d'abord à un cas légèrement plus simple, à savoir l'itération sur un tableau bidimensionnel. Dans ce cas, les deux dimensions sont parcourues chacune par un indice entier (p.ex. i pour la première, j pour la seconde). Une fois que vous avez bien compris cette version simplifiée, la version décrite ci-dessus où l'itérateur joue le rôle du second indice (j dans l'exemple) devrait être plus facile à comprendre.

En combinant ces différentes observations, on obtient le code suivant pour la classe de l'itérateur (qui est bien entendu imbriquée dans la classe SimpleHashSet, qui n'est pas montrée ci-dessous pour alléger la présentation) :

private static final class SHSIterator<E> implements Iterator<E> {
    private final ListSet<E>[] table;
    private int remaining;
    private int i;
    private Iterator<E> it;

    public SHSIterator(ListSet<E>[] table, int size) {
        this.table = table;
        this.remaining = size;
        this.i = 0;
        this.it = table[i].iterator();
    }

    @Override
    public boolean hasNext() {
        return remaining > 0;
    }

    @Override
    public E next() {
        if (! hasNext())
            throw new NoSuchElementException();
        --remaining;
        while (! it.hasNext())
            it = table[++i].iterator();
        return it.next();
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }
}

La solution pour cette première version se trouve dans la classe SimpleHashSet.

En rendant l'itérateur non statique, on a la possibilité de simplifier passablement son code puisqu'il n'a plus besoin de constructeur pour obtenir la table et sa taille, ni de paramètre de type. Les uns et les autres sont en effet accessibles directement via l'instance englobante.

La méthode remove devient particulièrement simple à mettre en œuvre, car il lui suffit d'appeler la méthode remove de l'itérateur it avant de décrémenter la taille de l'ensemble, stockée dans le champ size de l'instance englobante. La version statique de l'itérateur n'avait pas accès à ce champ.

Notez que contrairement à la méthode remove de la classe SimpleHashSet elle-même, qui ne sait pas si l'élément qu'elle a reçu est bien dans l'ensemble et doit donc ruser un peu pour mettre à jour la taille, la méthode remove de l'itérateur supprime toujours un élément, le dernier retourné par next, et peut donc sans hésiter décrémenter la taille.

private final class SHSIterator implements Iterator<E> {
    private int remaining = size;
    private int i = 0;
    private Iterator<E> it = table[i].iterator();

    @Override
    public boolean hasNext() { /* comme avant */ }

    @Override
    public E next() { /* comme avant */ }

    @Override
    public void remove() {
        it.remove();
        --size;
    }
}

La solution pour cette seconde version se trouve dans la classe SimpleHashSet2.

Pour rendre l'itérateur anonyme il suffit de déplacer son corps après l'énoncé new de la méthode iterator de la classe SimpleHashSet. On obtient donc le code suivant :

public class SimpleHashSet3<E> implements Set<E> {
    private int size;
    private ListSet<E>[] table;

    // … autres méthodes

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private int remaining = size;
            private int i = 0;
            private Iterator<E> it = table[i].iterator();

            @Override
            public boolean hasNext() { /* comme avant */ }

            @Override
            public E next() { /* comme avant */ }

            @Override
            public void remove() { /* comme avant */ }
        };
    }

    private ListSet<E> listFor(E elem) {
        return table[Math.abs(elem.hashCode() % table.length)];
    }
}

La solution pour cette troisième version se trouve dans la classe SimpleHashSet3.