:: Enseignements :: Master :: M1 :: 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 - DynamicIntHashSet

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èreent 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.

Toute optimisation commence par la construction d'un test de performance. Nous souhaitons tester la méthode contains en ayant une probabilité de succès de 50 %. Pour cela, on crée une liste de 10 000 entiers (utilisez la class java.util.Random pour produire les entiers aléatoires). Nous ajoutons (de façon aléatoire toujours en utilisant Random pour que le test soit reproductible) 50 % de ces entiers dans notre table. Le test consiste à mesurer avec java.lang.System.nanotime le temps pris par le test d'appartenance de l'ensemble des 10000 chaînes à la table.
Expliquer pourquoi il faut récupérer la valeur de retour de contains() lors du test ?
Créer une classe DynamicIntHashSet et modifier la méthode add pour implanter l'algorithme d'agrandissement de la table décrit ci-dessus.
Ecrire une méthode addAll, qui permet de recopier un DynamicIntHashSet dans le DynamicIntHashSet courant.
Faites les refactoring qui s'impose.
Ecrire une méthode intersect qui renvoie vrai si deux DynamicIntHashSet ont au moins un entier en commun.
Expliquer pourquoi il est intéressant de regarder le nombre d'élements de chaque DynamicIntHashSet avant d'effectuer l'algorithme.

Exercice 3 - Bloom Filter

On cherche à aller encore un peu plus vite. Lorsque l'on cherche un élement qui n'est pas présent, on peut avoir à parcourir plusieurs élements de la struture de données car il y a des collisions. Pour éviter ce problème, nous allons utiliser ce que l'on appelle un Bloom Filter (enfin une sorte de) qui permet de réduire un peu les collisions (attention, il ne les élimine pas). L'idée consiste à utiliser un bit set où l'on va allumer un bit calculé à partir de la fonction de hachage lorsque l'on ajoute un élement. Lors de la recherche d'un élement, on testera d'abord si le bit correspondant est allumé.

Sachant qu'il existe une classe java.util.BitSet, implanter le Bloom Filter en réutilisant le code de la classe DynamicIntHashSet dans une nouvelle classe FasterDynamicIntHashSet. On dimensionnera la taille du bit set à deux fois la taille du tableau. Est-ce plus efficace ?