Hacher menu

Exercice 1 - Maven

       <project xmlns="http://maven.apache.org/POM/4.0.0"
                xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/maven-4.0.0.xsd">

         <modelVersion>4.0.0</modelVersion>
         <groupId>fr.uge.set</groupId>
         <artifactId>set</artifactId>
         <version>0.0.1-SNAPSHOT</version>

         <properties>
           <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
         </properties>

         <dependencies>
           <dependency>
             <groupId>org.junit.jupiter</groupId>
             <artifactId>junit-jupiter-api</artifactId>
             <version>5.10.0</version>
             <scope>test</scope>
           </dependency>
         </dependencies>

         <build>
           <plugins>
             <plugin>
               <groupId>org.apache.maven.plugins</groupId>
               <artifactId>maven-compiler-plugin</artifactId>
               <version>3.11.0</version>
               <configuration>
                 <release>21</release>
               </configuration>
             </plugin>

             <plugin>
               <groupId>org.apache.maven.plugins</groupId>
               <artifactId>maven-surefire-plugin</artifactId>
               <version>3.1.2</version>
             </plugin>
           </plugins>
         </build>
       </project>
     

Exercice 2 - HashTableSet

     0:  [null]
     1:  [null]
     2:  [] -> Entry("Jane", null)
     3:  [null]
    

     0:  [null]
     1:  [null]
     2:  [] -> Entry("Jane", null)
     3:  [] -> Entry("John", null)
    

     0:  [null]
     1:  [null]
     2:  [] -> Entry("Arthur", ) -> Entry("Jane", null)
     3:  [] -> Entry("John", null)
    

1. Quels doivent être les champs de la classe Entry correspondant à une case d'une des listes chaînées utilisées par table de hachage
   Note : on va pas utiliser java.util.LinkedList, car on veut une liste simplement chaînée.
   Rappeler quelle est l'intérêt de déclarer Entry comme membre de la classe HashTableSet plutôt que comme une classe à coté dans le même package que HashTableSet ?
   Ne pourrait-on pas utiliser un record plutôt qu'une classe, ici ? Si oui, pourquoi ? Si non, pourquoi ?
   Écrire la classe HashTableSet dans le package fr.uge.set et ajouter Entry en tant que classe interne.
   Vérifier que les tests marqués "Q1" passent.


2. On souhaite maintenant ajouter un constructeur sans paramètre, une méthode add qui permet d'ajouter un élément non null et une méthode size qui renvoie le nombre d'éléments insérés (avec une complexité en O(1)).
   Pour l'instant, on va dire que la taille du tableau est toujours 16, on fera en sorte que la table de hachage s'agrandisse toute seule plus tard.
   Dans la classe HashTableSet, implanter le constructeur et les méthodes add et size.
   Vérifier que les tests marqués "Q2" passent.
   ATTENTION : add ne doit pas permettre d'ajouter deux fois le même élément, un ensemble/set ne permet pas les doublons.
   


3. On cherche maintenant à implanter une méthode forEach qui prend en paramètre une fonction. La méthode forEach parcourt tous les éléments insérés et pour chaque élément, appelle la fonction prise en paramètre avec l'élément courant.
   Quelle doit être la signature de la functional interface prise en paramètre de la méthode forEach ?
   Quel est le nom de la classe du package java.util.function qui a une méthode ayant la même signature ?
   Écrire la méthode forEach.
   Vérifier que les tests marqués "Q3" passent.
   Note : si vous êtes balèze, forEach peut s'écrire avec un Stream.


4. On souhaite maintenant ajouter une méthode contains qui renvoie si un objet pris en paramètre est un élément de l'ensemble ou pas, sous forme d'un booléen.
   Expliquer pourquoi nous n'allons pas utiliser forEach pour implanter contains (Il y a deux raisons, une algorithmique et une spécifique à Java).
   Écrire la méthode contains.
   Vérifier que les tests marqués "Q4" passent.


5. On veut maintenant faire en sorte que la table de hachage se redimensionne toute seule. Pour cela, lors de l'ajout d'un élément, on peut avoir à agrandir la table pour garder comme invariant que la taille du tableau est au moins 2 fois plus grande que le nombre d'éléments.
   Pour agrandir la table, on va créer un nouveau tableau deux fois plus grand et recopier touts les éléments dans ce nouveau tableau à la bonne place. Ensuite, il suffit de remplacer l'ancien tableau par le nouveau.
   Expliquer pourquoi, en plus d'être plus lisible, en termes de performance, l'agrandissement doit se faire dans sa propre méthode.
   Modifier votre implantation pour que la table s'agrandisse dynamiquement.
   Vérifier que les tests marqués "Q5" passent.
   Note : vous pouvez utiliser forEach pour parcourir les éléments de l'ancienne table.


6. L'implantation actuelle a un problème : même si on n'ajoute que des String lorsque l'on utilise forEach, l'utilisateur va probablement devoir faire des cast parce que les éléments envoyés par forEach sont typés Object.
   Par exemple, si on veut vérifier que toutes les chaînes de caractères contenues dans un ensemble commencent par "f", le code ci-dessous ne fonctionne pas

       var set = new HashTableSet();
       set.add("foo");
       set.add("five");
       set.add("fallout");
       set.forEach(element -> assertTrue(element.startsWith("f")));
      

   Pour que ce code fonctionne, il faut dire que le type des éléments que l'on ajoute avec add et le type des éléments que l'on reçoit dans la lambda du forEach est le même. Pour cela, il faut déclarer HashTableSet comme un type paramétré.
   Rappeler pourquoi en Java, il n'est pas possible de créer un tableau de type paramétré ? Quel est le work around ? Pourquoi celui-ci génère-t-il un warning ? Et dans quel cas et comment peut on supprimer ce warning ?
   Mettez en commentaire votre ancien code, puis dupliquez-le pour faire les changements qui permettent d'avoir un ensemble paramétré par le type des ses éléments.
   Vérifier que les tests marqués "Q6" passent.
   Attention: il faut que les tests écrits précédemment continuent de compiler (avec des warnings), donc les changements que vous effectuez doivent être rétro-compatibles avec l'ancienne version de votre code.


7. En fait, la signature de la méthode forEach que vous avez écrite n'est pas la bonne. En effet, forEach appelle la lambda avec des éléments de type E, donc la fonction peut prendre en paramètre des valeurs qui sont des super-types de E.
   Regarder comme on déclare un super-type dans un type paramétré en regardant la javadoc de la méthode forEach de ArrayList.
   Modifier votre code en conséquence.
   Vérifier que les tests marqués "Q7" passent.


8. On souhaite maintenant écrire une méthode addAll qui permet d'ajouter tous les éléments d'un HashTableSet dans le HashTableSet courant.
   Note : les éléments du HashTableSet pris en paramètre peuvent être des sous-types du type du HashTableSet courant. Si vous ne savez pas comment déclarer un sous-type dans un type paramétré, vous pouvez regarder la méthode Collection.addAll() des API du JDK.
   Écrire la méthode addAll.
   Vérifier que les tests marqués "Q8" passent.


9. Enfin, pour les plus balèzes, on souhaite pouvoir tester si deux HashTableSet sont égaux avec la méthode equals.
   Modifier votre code en conséquence.
   Vérifier que les tests marqués "Q9" passent.