:: Enseignements :: ESIPE :: E4INFO :: 2014-2015 :: Java Avancé ::

Implantation d'une table de hachage, classe interne

Le but de ces deux exercices est d'implanter une représentation d'un ensemble d'entiers sans doublons.
Comme les entiers ne sont pas forcément consécutifs, ils n'est pas possible d'utiliser un tableau ou un bitset pour représenter les valeurs (explosion en mémoire) ni une liste (algo en O(n)), on utilisera donc une table de hachage où les collisions sont stockées dans une liste chainée.
La taille de la table de hachage sera toujours une puissance de 2 (2, 4, 8, 16, 32, etc) pour permettre l'écriture d'une fonction de hachage rapide.
Dans le premier exercice, on considerera que la table de hachage a une taille fixe, puis pour le second exercice que la table de hachage doit grandir dès qu'elle est à moitié pleine.
On souhaite que les deux tables de hachage aient les opérations suivantes:

add qui permet d'ajouter un entier à l'ensemble (si il n'est pas déjà présent).
contains qui renvoie vrai si l'entier est dans l'ensemble.
size qui renvoie le nombre d'entiers contenus dans l'ensemble.
forEach() qui prend une lambda en paramètre, celle-ci sera appelée pour chaque entier présent dans l'ensemble.

Note: le but du TD est de ré-écrire une table de hachage, pas d'en utiliser une qui existe déjà, donc pour ce TD, nous n'utiliserons aucune des classes de java.util.

Exercice 1 - IntHashSet

Nous allons, dans un premier temps, implanter l'ensemble d'entiers en utilisant une table de hachage qui, s'il y a collision stocke les élements dans une liste chainée.
Pour les besoins du TP, nous allons, pour l'instant, fixer la taille de la table de hachage à 2 mais on vous demande d'écrire le code en présupposant seulement que la taille est une puissance de 2.

Les tests JUnit de cet exercice sont IntHashSetTest.java.

Quels doivent être les champs de la classe Entry correspondant à une case de la table de hachage sachant que l'on veut stocker les collisions dans une liste chainée.
On cherche à écrire la classe Java Entry correspondante. Quelle doit être la visibilité de cette classe ? Quels doivent être les modificateurs pour chaque champ ?
Ecrire la classe Entry.
Comment écrire la fonction de hachage dans le cas où la taille de la table est 2 sachant que l'on peut regarder le bit le plus à droite (celui des unités) pour savoir si l'on doit stocker les élements dans la case 0 ou 1.
En suivant la même idée, modifier votre fonction de hachage dans le cas où la taille de la table est une puissance de 2.
Ecrire la classe IntHashSet et implanter sa méthode add.
On souhaite que la classe Entry soit maintenant une classe interne de la classe IntHashSet. Que doit-on faire ?
Attention: Penser à bien supprimer le fichier Entry.java contenant l'ancienne classe.
Ecrire la méthode size avec une implantation en O(1).
On cherche maintenant à implanter la méthode forEach, quelle doit être la signature de la fonctional interface prise en paramètre de la méthode forEach.
Quel est le nom de la classe du package java.util.function qui a une méthode ayant la même signature ?
Ecrire la méthode forEach.
Ecrire la méthode contains.

Exercice 2 - IntLRUHashSet

On souhaite que, en moyenne, la table soit toujours à moitié vide pour éviter que les listes chainées qui gère les colisions soit trop longues. Pour cela, on vous demande d'agrandir la table de hachage si le nombre d'élements stockés est supérieur à la moitié de la taille de la table de hachage
L'algorithme classique d'agrandissement d'une table de hachage est lent, car il faut non seulement doubler la taille mais aussi pour chaque liste chainées re-répartir l'ensemble des valeurs contenue dans ces listes car des valeurs qui colisionnaient pour une taille de la table de hachage ne sont plus forcément en colision avec une nouvelle taille.
Pour éviter de re-repartir les valeurs, nous allons utiliser une astuce qui consiste lors du doublement de la taille à stocker dans les cases paires et impaires consécutives de la nouvelle table de hachage la même référence sur la liste chainée que la case correspondante dans l'ancienne table de hachage.

      par exemple, si on a une table de hachage
      
        -----
        |   | -> (2 , null)
        -----
        |   | -> null
        -----
      
      et que celle-ci est redimensionnée, on obtient
      
        -----
        |   | ----------------------> (2 , null)
        -----              /   
        |   | -> null     /
        -----            /
        |   | ----------/
        -----
        |   | -> null
        -----
        
      avec les deux premières cases pointant vers la même liste.

Les tests JUnit de cet exercice sont IntLRUHashSetTest.java.

Expliquer pourquoi l'astuce décrite plus haut marche lorsque l'on redimensionne la table ?
Créer un classe IntLRUHashSet et modifier la méthode add pour ajouter le code d'agrandissement de la table décrit ci-dessus.
Expliquer pourquoi forEach ne marche plus.
On se propose de résoudre le problème du forEach en marquant les Entry qui ont déjà été vues lors du parcours du forEach. Une Entry ne devra alors être envoyée au consumer que si elle n'a pas encore été marquée.
Pour marquer les Entry, nous n'allons pas utiliser un boolean car il faudrait le remettre à false avant ou après le parcours ce qui sera trop coûteux mais plutôt un entier.
L'idée est la suivante, la classe IntLRUHashSet va elle aussi posséder un entier qui, par défaut, sera initialisé à -1. Lors du parcours, si l'entier à l'intérieur d'une Entry est différent de l'entier du IntLRUHashSet alors on sait que l'Entry n'a pas encore été visitée. Une fois visité, on positionne l'entier dans l'Entry à la valeur de l'entier dans IntLRUHashSet. Lors d'une prochaine visite, comme l'entier de l'Entry et celui du IntLRUHashSet seront égaux, l'Entry sera considéré comme déjà visité. Il faut aussi qu'à la fin du parcours, pour les prochains parcours l'entier de IntLRUHashSet soit incrémenté.
Modifier la méthode forEach pour implanter cet algorithme de marquage.
Expliquer pourquoi si, lors d'un add ou d'un contains dans le cas où l'Entry existe déjà, on remonte celle-ci en tête de la liste chainée, on obtient le même résultat que si l'on avait utilisé algorithme classique de redimensionnement de la liste chainée.
Rappeler en donnant l'algorithme en pseudo-code, comment faire pour supprimer puis insérer l'Entry en début de liste quand celle-ci est simplement chainée. Pourquoi le premier élément de la liste est un cas particulier ?
Modifier la méthode add pour utiliser l'algorithme qui remonte l'Entry en tête de liste.
Faites de même avec la méthode contains.