Série 4 – Ensembles par hachage
Cette série est la quatrième du micro-projet consacré aux collections. Comme pour les séries précédentes vous placerez tout votre code dans le paquetage ch.epfl.collections.
Le but de cette série est de compléter votre bibliothèque de collections en y ajoutant une nouvelle mise en œuvre des ensembles génériques, utilisant la technique du hachage vue au cours. La classe à écrire, nommée HashSet, implémente l'interface Set de la semaine précédente.
Comme d'habitude, nous vous proposons de procéder de manière progressive, en commençant par une version relativement simple qui est augmentée petit-à-petit. Bon travail !
Version de base
La version de base de votre classe HashSet doit mettre en œuvre les ensembles génériques au moyen d'une table de hachage. Vous devez écrire la totalité des méthodes de l'interface Set, sauf iterator qui peut simplement retourner null pour l'instant.
Après avoir écrit le code, vérifiez que les tests qui n'utilisent pas l'itérateur fonctionnent.
Itération
La version de base terminée, modifiez la méthode iterator pour qu'elle retourne un itérateur sur les éléments de l'ensemble plutôt que null. Comme la semaine dernière, il n'est pas nécessaire que cet itérateur offre une méthode remove fonctionnelle, celle-ci peut se contenter de lever l'exception UnsupportedOperationException.
Les méthodes hasNext et next doivent quant-à-elles se comporter comme spécifié dans la documentation de l'interface Iterator. En particulier, next doit lever l'exception NoSuchElementException si tous les éléments ont été parcourus.
Notez que le parcours des éléments de la table de hachage ressemble au parcours des éléments d'un tableau à deux dimensions, la première dimension étant le tableau sous-jacent, la seconde étant les listes chaînées stockées dans ce tableau.
Une fois votre itérateur terminé, vérifiez que le test qui l'utilise fonctionne correctement.
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 le nombre d'entrées dans la table (le facteur de charge, ou load factor en anglais) reste proche d'une valeur considérée comme idéale. Un facteur de charge de 0.75 est bon, et votre mise en œuvre doit donc essayer de le maintenir proche de cette valeur.
Pour ce faire, modifiez vos méthodes add et remove afin qu'elles fassent un rehachage de la table si le facteur de charge est inférieur à 0.5 ou supérieur à 1. Pour effectuer ce rehachage, il faut créer un nouveau tableau sous-jacent dont la taille soit telle que le facteur de charge après rehachage soit aussi proche de 0.75 que possible, puis replacer tous les éléments de l'ensemble dans ce nouveau tableau sous-jacent.
Pour éviter des rehachages trop fréquents lorque l'ensemble ne contient que peu d'éléments, ne faites jamais descendre la taille de votre tableau sous-jacent en-dessous d'une certaine limite, p.ex. 10.
Pour effectuer le rehachage, nous vous conseillons d'allouer le nouveau tableau sous-jacent puis de parcourir les éléments de la table actuelle (p.ex. au moyen de la boucle for-each) et de les ajouter au nouveau tableau sous-jacent. Pour faire cet ajout, il faut calculer la position de l'élément dans le nouveau tableau, et l'insérer dans la liste correspondante. A noter qu'il ne faut pas tester si l'élément est déjà présent, puisque par définition l'ensemble en cours de rehachage ne contient pas de doublons.