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.14.4</version>
                 <scope>test</scope>
             </dependency>
         </dependencies>

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

             <plugin>
                 <groupId>org.apache.maven.plugins</groupId>
                 <artifactId>maven-surefire-plugin</artifactId>
                 <version>3.6.0</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 à un maillon des listes chaînées utilisées par table de hachage ?
   Rappeler quel est l'intérêt de déclarer Entry comme membre de la classe HashTableSet plutôt que comme une classe à côté dans le même package que HashTableSet ?
   Ne pourrait-on pas utiliser un record plutôt qu'une classe, ici ? Si oui, pourquoi ? Sinon, pourquoi ?
   Écrire la classe HashTableSet paramétrée par le type des éléments, dans le package fr.uge.set, son constructeur 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 nul et une méthode size qui renvoie le nombre d'éléments déjà 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.
   Expliquer pourquoi en Java, on ne peut pas créer de tableau de type paramétré ? Comment allons-nous faire alors ?
   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. En fait, la signature de la méthode forEach que vous avez écrite n'est peut-être pas la bonne. En effet, forEach est une méthode publique qui prend en paramètre un type paramétré, donc les règles PECS s'appliquent.
   Modifier la signature de votre méthode en conséquence.
   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 tous 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. 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.
   Quel doit être le type du paramètre de contains() ?
   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 "Q6" passent.


7. On souhaite maintenant écrire une méthode addAll qui permet d'ajouter tous les éléments d'un HashTableSet dans le HashTableSet courant.
   Écrire la méthode addAll.
   Vérifier que les tests marqués "Q7" passent.


8. 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 "Q8" passent.