:: Enseignements :: Master :: M1 :: 2011-2012 :: Java Avancé ::

Hash or Ash

On souhaite developper un programme intégré aux browsers Web permettant de savoir si un site Web est un site de phishing ou non pour en interdire l'accès à l'utilisateur sans ralentir le browser Web.
Pour cela, on testera le programme en simulant une sorte de table hachage de dizaine de milier sites Web frauduleux monté en mémoire (dans la vrai vie, on ne stocke pas la table en mémoire).

Les tests JUnit des exercices sont HashTest.java et Hash2Test.java et Hash3Test.java.

Exercice 1 - My first Hash

On cherche dans un premier temps, à écrire une classe Hash permettant de stocker des chaîne de caractères et de vérifier si une chaine de caractères est stockée par la classe.

Rappeler la différence entre le hachage ouvert (open hashing) et le hachage fermé (Wikipedia si vous avez du mal).
Pour la suite de l'exercice, nous utiliseront le hachage fermée qui s'il y a collision stocke l'élement dans la case suivante de plus nous nous contenterons d'une structure de donnée qui ne se redimensionne pas. Ecrire un constructeur prenant en paramètre un nombre maximum d'élement et une méthode add permettant d'ajouter des chaînes de caractères.
Que faire si la table est pleine ? Implanter la solution retenu.
Ecrire la méthode toString.
Ecrire une méthode contains qui renvoie vrai si l'élement est dans la structure de donnée.

Exercice 2 - My second Hash

On cherche à vouloir optimiser la structure de donnée du premier exercice. On créera pour cela une nouvelle classe nommée Hash2.

Sachant que l'on veut utiliser la structure de donnée pour stocker les sites de phishing, quelle est la ou les méthodes à optimizer ?
Avant d'optimizer quoi que cela soit, il nous faut un test de performance. Ecrire un test qui génère 10 000 nombres sous forme de chaîne de caractères dans une liste. De plus, de facon aléatoire certaines des mêmes chaînes de caractères devront être stockées dans un Hash2 de tel façon que en moyenne le Hash2 stoque la moitié des chaînes de caractères. Vous utiliserez pour cela la classe java.util.Random en faisant que les résulats soient reproductibles. Le test devra afficher le temps en nano-seconde (java.lang.System.nanoTime) qu'il faut pour parcourir la liste et vérifier si la châine de caractères est présente ou non dans le Hash2.
Expliquer pourquoi il faut récupérer la valeur de retour de contains() lors du test ?
Modifier votre code pour ne lire les champs de l'objet qu'une fois par méthode en stockant ceux-ci dans des variables locales si besoin.
Est-ce plus efficace ?
On veut supprimer l'opération de modulo pour gagner un peu de temps, pour cela on s'arrage pour que la taille du tableau soit une puissance de deux et dans ce cas on peut utiliser un et bits à bits à la place. Expliquer pouquoi et comment ?
Comment trouver la puissance de 2 supérieurs à un nombre donnée Sachant qu'il existe en Java une méthode Integer.highestOneBit ? Ecrire le code correspondant.
Modifier l'implantation de Hash2 pour ne plus utiliser de modulo.
Est-ce plus efficace ?

Exercice 3 - My third Hash

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ée car il y a des collisions. Pour éviter ce problème, nous allons utiliser ce qu'on appel 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 Hash2 dans une nouvelle classe Hash3. On dimensionnera la taille du bit set à deux fois la taille du tableau.
Est-ce plus efficace ?

Exercice 4 - A la maison

On souhaite écire un script ANT, permettant de compiler l'ensemble des sources et d'exécuter le test de performance. Pour plus d'informations, regarder du côté de cette aide et du manuel en ligne

Ecrire une target clean qui efface l'ensemble des fichiers .class du répertoire classes et qui crée celui-ci s'il n'existe pas.
Ecrire une target compile qui compile l'ensemble des fichiers sources stockées dans le repertoire src dans le répertoire classes. Vérifier que les numéros de ligne correspondnant aux instructions sont bien ajoutées par le compilateur (si vous levez une exception vous devez avoir afficher les numéros de lignes).
Pourquoi il ne faut pas de dépendence entre compile et clean ?
Ecrire une target run qui lance le test de performance. Mettre les dépendances comme il faut.
Ecrire une target junit qui lance les tests unitaires. Ajuster les dépendances.
Optionnel si vous êtes baleze, faire en sorte que le même test de performance se lance sur Hash, Hash2 et Hash3 en modifiant le test pour qu'il prennent en paramètre la classe à tester.
Voir Class.forName, Class.getConstructors() et Constructor.newInstance.