Examen de Java Avancé 2025 - TP noté

Exercice 1 - OrderedMap

      var map = new LinkedHashMap<String, Integer>();
      map.put("alpha", 11);
      map.put("beta", 22);
      map.put("gamma", 33);
      map.put("delta", 44);
      var orderedMap = OrderedMap.of(map);

      IO.println(orderedMap.size());  // 4
      IO.println(orderedMap.get("beta"));  // 22
      IO.println(orderedMap.keySet());  // [alpha, beta, gamma, delta]
      IO.println(orderedMap.values());  // [11, 22, 33, 44]
     

1. On souhaite écrire la méthode of(map), qui prend une Map en paramètre et renvoie une nouvelle instance de OrderedMap ainsi que la méthode size qui renvoie le nombre de couples clé/valeur.
   Il ne doit pas être possible de créer une instance de OrderedMap autrement qu'en utilisant of(map).
   Sachant qu'en terme d'implantation, on veut stocker les couples clé/valeur dans un tableau de Map.Entry, écrire la classe OrderedMap.
   Vérifier que les tests unitaires marqués Q1 passent.
   Rappel : en Java, il existe deux façons de créer des Map.Entry, soit en utilisant la méthode Map.entry(key, value) soit en utilisant le constructeur de la classe SimpleImmutableEntry (cette classe est déclarée en tant que classe interne de la classe AbstractMap).


2. On souhaite que la classe OrderedMap soit une Map.
   Dans ce but, modifier le code de la classe OrderedMap, sans ajouter de nouveaux champs.
   Vérifier que les tests unitaires marqués Q2 passent.
   Rappel : en Java, il existe la classe abstraite AbstractMap.


3. Dans le code ci-dessous, le Stream renvoyé n'est pas implanté correctement.

   OrderedMap<String, Integer> orderedMap = ...
   var stream = orderedMap.entrySet().stream();
         

   
   Quelle méthode doit-on redéfinir pour changer cette implantation ?
   Sachant que pour l'instant, on ne s'intéresse qu'à la partie séquentielle de l'implantation, modifier le code de la classe OrderedMap pour que le Stream créé sur un ensemble renvoyé par la méthode entrySet() soit correct.
   Vérifier que les tests unitaires marqués Q3 passent.


4. Notre classe OrderedMap a pour l'instant une implantation de la méthode get(key) qui est linéaire. On voudrait changer cette implantation pour avoir un implantation en O(1) en moyenne.
   Pour cela, on se propose d'ajouter à la classe OrderedMap, un second tableau contenant des entiers, d'une taille double de la taille du tableau de couples clé/valeur. Ce tableau se comporte comme une table de hachage des clés. Il contient, pour chaque couple clé/valeur, son index (plus exactement son index + 1) dans le tableau des couples clé/valeur. En cas de collisions l'index sera stocké dans les case suivantes (en considérant le tableau comme circulaire).
   Par exemple, supposons que notre OrderedMap stocke les couples ("alpha", 11), ("beta", 22), ("gamma", 33) et ("delta", 44). Notre tableau d'entiers va contenir 8 cases, toutes initialisées à 0. Puis, on va insérer "alpha", son hashCode modulo 8 est 6, donc dans la case 6, on met l'index 1 car c'est le premier couple. Pour "beta", le hashCode modulo 8 est 0, donc dans la case 0, on met l'index 2 (c'est le second couple). Le hashCode de "gamma" modulo 8 est 7, donc dans la case 7, on met l'index 3 (c'est le 3e couple). Enfin pour "delta", le hashCode modulo 8 est 0, mais il y a déjà une valeur dans la case 0, donc on met l'index 4 dans la case suivante (la case 1).
   À la fin, le tableau d'entiers est [2, 4, 0, 0, 0, 0, 1, 3].
   Avant d'ajouter un champ contenant ce tableau d'entiers à OrderedMap, on va écrire une méthode d'aide indexArray(entries) qui prend en paramètre un tableau des couples clé/valeur et renvoie le tableau d'index correspondant en utilisant l'algorithme décrit ci-dessus (attention au cas où le hashCode est négatif).
   Écrire la méthode indexArray(entries).
   Vérifier que les tests unitaires marqués Q4 passent.


5. On peut maintenant ajouter dans OrderedMap un champ qui contient le tableau d'index. Le tableau ne devra être calculé que si cela est nécessaire ! Par exemple, lorsque l'on appelle get(key).
   Implanter get et getOrDefault pour que si le tableau d'index n'existe pas, celui-ci soit créé puis utilisé pour aller chercher rapidement la valeur associée à une clé.
   Vérifier que les tests unitaires marqués Q5 passent.


6. On peut remarquer que l'implantation de containsKey(key) a aussi un problème de complexité.
   Modifier l'implantation de containsKey pour améliorer leur complexité.
   Vérifier que les tests unitaires marqués Q6 passent.


7. On peut remarquer qu'un Stream créé sur le keySet() d'une OrderedMap n'est pas correct.
   On peut aussi remarquer que le Stream du keySet() et le Stream de l'entrySet() peuvent utiliser le même Spliterator (configurés différemment).
   Faite les changements qui s'imposent en réutilisant le même Spliterator.
   Vérifier que les tests unitaires marqués Q7 passent.


8. Enfin, notre Spliterator ne supporte pas le calcul en parallèle... modifiez-le pour qu'il soit supporté.
   Vérifier que les tests unitaires marqués Q8 passent.