Série 6 – Ensembles par hachage

Introduction

Le but de cette série, la seconde du mini-projet collections, est de terminer la mise en œuvre de la version simple des ensembles par hachage vue au cours.

Pour démarrer, nous vous fournissons une archive Zip contenant la totalité du code donné dans le cours, ainsi que deux fichiers de test. A noter que si vous créez un nouveau projet pour cette série vous devrez :

  1. Demander à Eclipse d'utiliser le répertoire test comme répertoire source, en faisant un clic droit dessus dans l'explorateur de paquetages (Package Explorer) puis en choisissant l'entrée Use as Source Folder du sous-menu Build Path.
  2. Ajouter JUnit aux bibliothèques, ce qui implique d'aller dans la section Java Build Path des propriétés du projet, d'ouvrir l'onglet Libraries, de cliquer sur Add Library… et de sélectionner JUnit dans la liste.

Exercice 1 – itérateur d'ensemble

La classe SimpleHashSet contient la mise en œuvre partielle (et relativement peu efficace) des ensembles par table de hachage vue au cours. Seul le corps de la classe de l'itérateur manque. Le but de cet exercice est de compléter cette classe puis de la transformer en classe imbriquée normale, puis anonyme.

Itérateur statique

Dans un premier temps, complétez le code des méthodes hasNext et next de l'itérateur donné. La méthode remove de cet itérateur lève l'exception UnsupportedOperationException, et pour l'instant il ne vous est pas demandé d'essayer de la mettre correctement en œuvre.

L'itérateur sur les tables de hachage fait un parcours en deux dimensions, dans le sens où il parcourt d'une part le tableau contenant les listes-ensembles (instances de ListSet) et d'autre part chacune de ces listes-ensembles. Il est conseillé de stocker l'état de ce parcours dans trois champs de l'itérateur :

  1. Le champ remaining, présenté au cours, contenant le nombre d'éléments qui peuvent encore être fournis par l'itérateur et simplifiant beaucoup l'écriture de la méthode hasNext.
  2. Un entier contenant la position de la liste-ensemble à parcourir dans le tableau (première dimension du parcours).
  3. Un itérateur itérant sur la liste-ensemble qui se trouve à la position donnée par le champ précédent dans le tableau (seconde dimension du parcours).

Une fois le code écrit, lancez les tests de la classe SimpleHashSetTest pour vous assurer que votre itérateur fonctionne correctement. Ils devraient tous s'exécuter sans erreur sauf ceux utilisant la méthode remove de l'itérateur, qui ne sera mise en œuvre correctement que plus tard.

Itérateur non statique

Transformez à présent la classe de l'itérateur SHSIterator en une simple classe imbriquée (c-à-d non statique), en enlevant le modificateur static de sa déclaration. Vous pouvez alors simplifier sa définition puisqu'elle n'a plus besoin de paramètre de type — le paramètre E de la classe englobante est maintenant visible — ni de constructeur pour obtenir la taille de l'ensemble ou la table de hachage.

D'autre part, cette version non statique de la classe SHSIterator peut modifier les champs de sa classe englobante. Cela permet de facilement écrire la méthode remove de l'itérateur, qui doit mettre à jour la taille de l'ensemble. Notez bien que, contrairement à la méthode remove de la classe SimpleHashSet, la méthode remove de l'itérateur enlève dans tous les cas un élément à l'ensemble, et la mise à jour de sa taille est donc très simple.

Ces modifications effectuées, relancez les tests pour vous assurer que votre itérateur est toujours correct, et que tous les tests passent dorénavant.

Itérateur anonyme

Finalement, étant donné que la classe SHSIterator n'est pas utilisée ailleurs que dans la méthode iterator de SimpleHashSet, transformez-la en classe anonyme.

Pour mémoire, cela implique de placer son corps directement après l'énoncé new, dans lequel le nom de la classe (ici SHSIterator) est remplacé par le nom de la super-classe ou de l'interface implémentée par la classe anonyme (ici Iterator). En résumé, la méthode iterator ressemblera à ceci : 

public Iterator<E> iterator() {
    return new Iterator<E>() {
        // … corps de ce qui était la classe SHSIterator
    };
}

Lancez une dernière fois les tests pour vérifier que la version anonyme de votre itérateur se comporte correctement.

Exercice 2 – rehachage

Comme expliqué au cours, une table de hachage n'est efficace que si les listes qu'elle contient sont courtes, idéalement de longueur 1.

Il n'y a pas de moyen infaillible de garantir que les listes restent courtes, car cela dépend à la fois de la fonction de hachage utilisée et des valeurs stockées dans la table. Au lieu de cela, on s'arrange plutôt pour que le rapport entre le nombre d'éléments de l'ensemble et la taille du tableau (le facteur de charge, ou load factor en anglais) reste proche d'une valeur considérée comme idéale.

Le but de cet exercice est de modifier la méthode add de la classe SimpleHashSet afin qu'elle garantisse que le facteur de charge ne dépasse jamais 1. Pour cela, elle doit calculer le facteur de charge après chaque ajout, et s'il est supérieur à 1, procéder à un rehachage.

Un rehachage implique l'allocation d'une nouvelle table, dont la taille doit être calculée pour que son facteur de charge soit proche de 0.75. Une fois la nouvelle table allouée, il faut y replacer tous les éléments se trouvant dans la table en cours de rehachage, et finalement remplacer la table actuelle par la nouvelle.

A noter qu'avec cette mise en œuvre, la taille de la table ne peut qu'augmenter, elle ne diminue jamais. Les tables de hachage de la bibliothèque Java ont le même comportement. On pourrait également diminuer la taille du tableau lorsque le facteur de charge descend en-dessous d'une valeur minimale, mais cela complique la mise en œuvre de la méthode remove de l'itérateur.