:: Enseignements :: Master :: M1 :: 2024-2025 :: Java Avancé ::

Examen de Java Avancé 2024 - session 2

Le but de ce TP noté est d'implanter une classe BloomSet qui est un ensemble qui possède une représentation compacte en mémoire quand il y a peu d'éléments dans l'ensemble.

Vos sources Java produites pendant l'examen devront être placées sous le répertoire EXAM de votre compte ($HOME) (qui est vide dans l'environnement de TP noté). Sinon, elles ne seront pas récupérées.

Tout document papier est proscrit.
La javadoc 23 est https://igm.univ-mlv.fr/~juge/javadoc-23/.
Les seuls documents électroniques autorisés sont les supports de cours à l'url http://igm.univ-mlv.fr/~forax/ens/java-avance/cours/pdf/.

Vous avez le droit de lire le sujet jusqu'au bout, cela vous donnera une bonne idée de là où on veut aller !

Exercice 1 - BloomSet

Un BloomSet est un ensemble (un Set) d'éléments non null qui stocke les éléments dans un tableau par défaut, c'est à dire quand il y a au plus 8 éléments. Et s'il y a plus de 8 éléments la représentation change pour utiliser une implantation déjà existante de Set (une de java.util).
Si le nombre d'éléments est inférieur ou égal à 8, pour éviter d'avoir à parcourir le tableau en cas d'ajout et/ou de test si un élément est présent, on va utiliser un entier bloomHash qui contient un "ou bit à bit" de l'ensemble des valeurs de hachage (hashCode) des éléments stockés dans l'ensemble.
Par exemple, si on stocke les éléments "toto", "titi", et "tata", et qu'on regarde les 6 derniers chiffres de l'écriture en binaire de leur hashCode, on obtient

        "toto" -> ..........................110110
        "titi" -> ..........................101010
        "tata" -> ..........................011010

Note : on prend ici les 6 derniers chiffres juste pour simplifier l'exemple, l'implantation utilise bien les 32 bits d'un entier.
Les 6 derniers chiffres du bloomHash sont donc

                  ..........................111110

car c'est un "ou" bit à bit des hashCodes des chaînes de caractères.
Maintenant supposons que l'on veut insérer "elephant" dans l'ensemble. La chaînes "elephant" a pour hashCode

                  ..........................010001

On sait donc que "elephant" ne fait pas partie de l'ensemble sans même regarder les différents éléments, car si "elephant" était dans l'ensemble, alors le bit le plus à droite du hashBloom devrait être un 1 et pas un 0.
Comme indiqué ci-dessus, nous allons nous servir de cette propriété pour améliorer la vitesse de l'algorithme d'ajout et de recherche.

Dans le cas où un BloomSet possède plus de 8 éléments, on change la représentation, car il y a de grandes chances qu'à ce stade, le champ hashBloom soit plein de 1, et donc qu'il ne serve plus à grand-chose. dans ce cas, la représentation devient un Set déjà existant dans le package java.util (à vous de choisir le bon).
De plus, comme on veut que la représentation d'un BloomSet soit compacte en mémoire, on ne stockera pas le nombre d'éléments dans le BloomSet pour éviter d'avoir un champ supplémentaire. En effet, au pire cas, on ne parcourt que 8 éléments.

Voici un exemple d'utilisation.

      BloomSet<String> bloomSet = new BloomSet<String>();
      bloomSet.add("one");  // true
      bloomSet.add("two");  // true
      bloomSet.add("one");  // false

      System.out.println(bloomSet.size());  // 2

      System.out.println(bloomSet.contains("one"));    // true
      System.out.println(bloomSet.contains("two"));    // true
      System.out.println(bloomSet.contains("three"));  // false

La classe BloomSet possède les méthodes suivantes

un constructeur sans paramètre qui permet de créer un BloomSet vide,
une méthode add(element) qui permet d'ajouter un élément et renvoie true si l'élément a été ajouté,
une méthode size qui renvoie le nombre d'éléments,
une méthode contains qui permet de savoir si une valeur fait partie de l'ensemble,
les autres méthodes non-modifiables de l'interface Set permettant de voir un BloomSet comme un ensemble.

On peut noter, qu'il ne doit pas être possible de supprimer un élément du BloomSet.

Des tests unitaires correspondant à l'implantation sont ici : BloomSetTest.java
Note : comme on utilise les tests unitaires JUnit sans Maven, dans la configuration de votre projet, il faut ajouter la librairie JUnit 5, soit à partir du fichier BloomSetTest.java, en cliquant sur l'annotation @Test et en sélectionnant le quickfix "Fixup project ...", soit en sélectionnant les "Properties" du projet (avec le bouton droit de la souris sur le projet) puis en ajoutant la librairie JUnit 5 (jupiter) au ClassPath.

Dans un premier temps, on va considérer qu'il n'y a pas plus de 8 éléments, donc utiliser un tableau de taille 8 suffit.
On souhaite implanter, le constructeur sans paramètre, la méthode add(element) et la méthode size. La méthode add ajoute un élément dans la première case vide du tableau et indique si l'élément a bien été ajouté au BloomSet en renvoyant true et false sinon. La méthode size renvoie le nombre d'éléments insérés.
Créer la classe BloomSet ainsi que les méthodes demandées.
Vérifier que les tests unitaires marqués Q1 passent.

On souhaite ajouter une méthode contains(object) qui renvoie true si l'objet pris en paramètre est un élément du BloomSet.
Écrire la méthode contains.
Vérifier que les tests unitaires marqués Q2 passent.

On souhaite accélérer l'implantation de add, pour cela, nous allons ajouter le champ bloomHash qui fonctionne comme décrit ci-dessus.
Modifier le code de la classe BloomSet en conséquence.
Vérifier que les tests unitaires marqués Q3 passent.

De façon similaire, on peut aussi modifier contains pour avoir une implantation plus efficace utilisant le champ bloomHash.
Modifier le code de la méthode contains.
Vérifier que les tests unitaires marqués Q4 passent.

On veut maintenant gérer le cas où l'on a plus de 8 éléments, dans ce cas, lors de l'ajout du 9-ième élément (pas avant !), on va changer la représentation pour utiliser une implantation de l'interface java.util.Set qui va stocker tous les éléments.
Quelle implantation de Set doit-on utiliser ici ?
Pour aider un peu le GC, on va éviter que les éléments soient stockés et dans le tableau et dans le Set en même temps. Cela va aussi simplifier l'écriture du code.
Faites les changements qui s'imposent.
Vérifier que les tests unitaires marqués Q5 passent.

On souhaite maintenant que la classe BloomSet implante l'interface Set.
Sachant qu'il existe la classe AbstractSet, modifier le code de BloomSet en conséquence.
Vérifier que les tests unitaires marqués Q6 passent.
Rappel : l'implantation ne doit pas permettre la suppression d'éléments.

Si vous ne l'avez pas déjà fait, on peut se rendre compte que l'implantation de isEmpty peut être optimisée pour être toujours en temps constant.
Vérifier que les tests unitaires marqués Q7 passent.

On peut aussi se rendre compte que l'on peut éviter de calculer la taille dans l'implantation de equals() si les deux objets sont des BloomSet mais qu'ils n'utilisent pas la même représentation.
Pareil si les deux BloomSet n'ont pas le même bloomHash.
Modifier la classe BloomSet en conséquence.
Vérifier que les tests unitaires marqués Q8 passent.

Enfin, le Spliterator renvoyé par la méthode spliterator() n'est pas implanté correctement.
En effet, on sait qu'un BloomSet ne peut pas stocker null et que si l'on a moins de 8 éléments, ceux-ci sont ordonnées,
Note : en terme d'implantation, si vous devez créer une classe, créer celle-ci en tant que classe locale à la méthode spliterator.
Écrire l'implantation de la méthode spliterator.
Vérifier que les tests unitaires marqués Q9 passent.