:: Enseignements :: ESIPE :: E4INFO :: 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é 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 et qui en stocke la moitié aussi dans Hash2 (penser à la classe java.util.Random). Puis afficher le temps en nano-seconde (java.lang.System.nanoTime) pour tester si un nombre est ou non stocker dans Hash2.
Expliquer pourquoi on doit par exemple compter le nombre d'élement effectivement contenu ?
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 au 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 ?
On cherche à trouver la puissance de 2 supérieurs à un nombre donnée. Une facon consiste à calculer le nombre de zéros à gauche du nombre dans sa représentation binaire (ceux non significatif) puis d'en déduire l'index du bit correspondant à la puissance de 2 supérieur.
Sachant qu'il y a tout ce dont vous révez dans java.lang.Integer, indiquer le code permettant de trouver la puissance de 2 supérieur d'un nombre.
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.