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

Hash or Ash

On souhaite développer 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 de hachage de dizaine de milliers de sites Web frauduleux montés en mémoire (dans la vraie 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înes de caractères et de vérifier si une chaîne 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 utiliserons le hachage ouvert qui, s'il y a collision, stocke l'élement dans une liste chaînée. De plus, nous nous contenterons d'une structure de données qui ne se redimensionne pas. Ecrire un constructeur prenant en paramètre un nombre maximum d'élements et une méthode add permettant d'ajouter des chaînes de caractères.
Pourquoi ne doit-on pas attendre que la table soit pleine ? Implanter la solution retenue.
Ecrire la méthode toString.
Ecrire une méthode contains qui renvoie vrai si l'élement est dans la structure de données.

Exercice 2 - My second Hash

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

Sachant que l'on veut utiliser la structure de données pour stocker les sites de phishing, quelle est la ou les méthodes à optimiser ?
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 chaînes construites à partir de la transformation d'entiers aléatoires en String (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 strings dans notre table. Le test consiste à mesurer avec java.lang.System.nanotime le temps pris par le test d'appartenance de l'ensemble des 10 000 chaînes à la table.
Expliquer pourquoi il faut récupérer la valeur de retour de contains() lors du test ?
Modifier votre code pour ne lire les champs des objets utilisés dans l'implantation de la table de hachage qu'une seule 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'arrange pour que la taille du tableau soit une puissance de deux et, dans ce cas, on peut utiliser un bit à bit à la place. Expliquer pouquoi et comment ?
Comment trouver la puissance de 2 supérieure à un nombre donné 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é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 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 écrire 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épendance 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 balèzes, faire en sorte que le même test de performance se lance sur Hash, Hash2 et Hash3 en modifiant le test pour qu'il prenne en paramètre la classe à tester.
Voir Class.forName, Class.getConstructors() et Constructor.newInstance.