:: Enseignements :: Master :: M1 :: 2021-2022 :: 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. Il faudra ré-organiser les élements lorsque la table de hachage grandie.
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 (que l'on va fabriquer nous-même, et pas en utilisant LinkedList).
On cherche à écrire la classe Java Entry correspondante dans le package fr.umlv.set. Quelle doit être la visibilité de cette classe ? Quels doivent être les modificateurs pour chaque champ ? En fait, ne pourrait-on pas utiliser un record plutôt qu'une classe, ici ? Pourquoi ?
Pour finir, il vaut mieux déclarer Entry en tant que classe interne de la classe IntHashSet plutôt qu'en tant que type dans le package fr.umlv.set .
Pourquoi ? Quelle doit être la visibilité de Entry ?
Écrire la classe IntHashSet dans le package fr.umlv.set et ajouter Entry en tant que classe interne.
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 ne connaissez pas, allez lire le chapitre 2 du Hacker's Delight.
Dans la classe IntHashSet, implanter la méthode add.
Écrire également 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 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.
L'idée est que si la longueur du tableau est inférieure à la moitié du nombre d’éléments, il faut doubler la taille du tableau et re-stocker tous les éléments (pas besoin de tester si un élément existe déjà dans le nouveau tableau).
Note : il faut que le champ contenant le tableau ne soit plus final.

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 ?