:: Enseignements :: ESIPE :: E4INFO :: 2015-2016 :: 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'éléments sans doublons.
Comme les éléments 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.
Note: si vous ne connaissez pas, allez lire le chapitre 2 du Hacker's Delight.
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 - DynamicHashSet

Pour optimiser notre table de hachage, on souhaite qu'en moyenne, la table soit toujours à moitié vide pour éviter que les listes chainées qui gèrent les colisions soient 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 consiste non seulement à doubler la taille mais aussi pour chaque liste chainée re-répartir l'ensemble des valeurs contenues 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.
Les tests JUnit de cet exercice sont DynamicHashSetTest.java.

Avant de rendre la taille de la table de hachage dynamique, nous allons generifier celle-ci pour permettre de stocker pas uniquement des entiers mais n'importe qu'elle valeur.
Avant de générifier votre code, quelle est le problème avec la création de tableau ayant pour type une variable de type ?
Comment fait-on pour résoudre le problème même si cela lève un warning.
Rappeler pourquoi on a ce warning et comment fait-on pour le supprimer puis expliquer si supprimer le warning ici est une connerie où pas.
Modifier le code de la méthode add pour implanter l'algorithme d'agrandissement de la table.
Note: essayer de ne pas mettre tout le code dans la méthode add.
Ecrire une méthode addAll, qui permet de recopier une collection d'élements dans le DynamicHashSet courant.
Regarder la signature de la méthode addAll dans java.util.Collection, avez vous la même signature ? Modifier votre code si nécessaire.
Expliquer ce que veux dire le '?' dans la signature de addAll
Ne devrait-on pas aussi utiliser un '?' dans la signature de la méthode forEach ?