:: Enseignements :: Master :: M1 :: 2019-2020 :: 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 (algos d'ajout/recherche/suppression en O(n)), on utilisera donc une table de hachage où les collisions sont stockées dans une liste chaîné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 considérera 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 éléments dans une liste chaînée.
Pour les besoins du TP, nous allons, pour l'instant, fixer la taille de la table de hachage à 8 mais on vous demande d'écrire le code en présupposant seulement que la taille est une puissance de 2.

Les tests JUnit 5 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 chaîné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 ?
Écrire la classe Entry dans le package fr.umlv.set.
Comment écrire la fonction de hachage dans le cas où la taille de la table est 2? Pourquoi est-ce que ça n'est pas une bonne idée d'utiliser l'opérateur %? Écrire une version "rapide" de la fonction de hachage
Indice: on peut regarder le bit le plus à droite (celui des unités) pour savoir si l'on doit stocker les éléments dans la case 0 ou 1.
Et si la taille de la table est 8?
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.
Note: si vous voulez en savoir plus sur les opérations bit à bit, vous pouvez lire le chapitre 2 du Hacker's Delight
Écrire la classe fr.umlv.set.IntHashSet et implanter sa méthode add.
Écrire également la méthode size avec une implantation en O(1).
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.
On cherche maintenant à implanter la méthode forEach. Quelle doit être la signature de la functional 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 ?
Écrire la méthode forEach.
Écrire la méthode contains.

Exercice 2 - DynamicHashSet

Pour optimiser notre table de hachage, on souhaite qu'en moyenne, la table soit toujours à moitié vide, de façon à éviter que les listes chaînées qui gèrent les collisions soient trop longues. Pour cela, on vous demande d'agrandir la table de hachage si le nombre d’éléments 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 chaînée, à re-répartir l'ensemble des valeurs contenues dans la liste car des valeurs qui entraient en collision pour une certaine taille de la table de hachage ne sont plus forcément en collision avec une nouvelle taille.
Les tests JUnit 5 de cet exercice sont DynamicHashSetTest.java.

Avant tout, nous souhaitons générifier notre table de hachage, pour permettre de ne pas stocker uniquement des entiers mais n'importe quel type de valeur.
Avant de générifier votre code, quelle est le problème avec la création de tableau ayant pour type un type paramétré ?
Comment fait-on pour résoudre le problème, même si cela lève un warning.
Rappeler pourquoi on a ce warning.
Peut-on supprimer le warning ici, ou est-ce une bêtise?
Comment fait-on pour supprimer le warning?
Reprendre et générifier le code de l'exercice précédent pour fabriquer une classe de table de hachage générique.
Vérifier la signature de la méthode contains de HashSet et expliquer pourquoi on utilise un type plus général que E.
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 et de ne pas dupliquer de code.
Si vous avez fait en sorte de ne pas dupliquer de code pour la question précédente, il est probable que vous ayez utilisé une ou plusieurs méthodes publiques de la classe DynamicHashSet à l'intérieur du code de la classe. Rappelez pourquoi c'est une mauvaise idée et proposez une solution pour éviter cela.

Exercice 3 - Wild cards (optionel)

Écrire une méthode addAll, qui permet de recopier une collection d’éléments 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 ?