Portail informatique Année 2018 – 2019

CSC 3101 – Algorithmique et langage de programmation

L'objectif de ce TP est d'étudier les listes doublement chaînées circulaires, les tables de hachages et les génériques en Java.

Durée des exercices obligatoires : 2h30 en présentiel + 45mn en hors présentiel
Avant de pouvoir partir en vacances à Bilbao, il faut être capable de retrouver les coordonnées GPS d'une ville à partir de son nom. En effet, dans le CI5, notre application manipule directement les structures de données représentant les villes, mais notre application devrait avant être capable de retrouver ces structures de données lorsque l'utilisateur saisit des noms de villes dans l'interface.

De façon générale, une structure associant des clés à des valeurs s'appelle une table d'associations (aussi appelé dictionnaire ou encore map en anglais). Dans cet exercice, notre table d'associations associe des noms de ville (les clés) à des coordonnées GPS (les valeurs). Les tables d'associations sont omniprésentes en informatique. Ces tables sont, par exemple, utilisées par de nombreux serveurs Web comme Facebook, Google ou Amazon afin de retrouver les données associées à un utilisateur à partir de son identifiant de connexion. Vous avez même déjà mis en œuvre une table d'associations en utilisant un arbre binaire de recherche lorsque vous avez conçu la banque Lannister en CI4 : cette structure nous servait à retrouver un compte en banque (une valeur) à partir d'un nom d'utilisateur (une clé).

Dans ce TP, nous étudions une nouvelle mise en œuvre de la table d'associations : la table de hachage (hashmap en anglais). La table de hachage est une structure de données particulièrement efficace. Dans le meilleur cas, elle permet de retrouver une valeur à partir de sa clé en un temps constant (c.-à.d indépendamment du nombre d'éléments dans la table). Le pire cas est proportionnel au nombre d'éléments et le cas moyen est en général proportionnel à une racine nième du nombre d'éléments, où n est une constante dépendante de la mise en œuvre.

Abstraitement, une table de hachage est un tableau de taille infinie contenant des couples clés/valeurs. Le principe est d'associer un numéro unique à chaque clé. Ce numéro s'appelle le code de hachage de la clé et correspond à l'entrée à laquelle se trouve le couple clé/valeur associé à la clé dans le tableau. La figure ci-dessous, dans laquelle seules les valeurs sont représentée, illustre le principe. À partir de la clé K, on calcule le code de hachage N qui est directement l'indice contenant le couple clé/valeur associé à la clé K dans le tableau. --------------------------------------------------- ...... Table | v0 | v1 | v2 | v3 | v4 | v5 | v6 | v7 | v8 | ...... --------------------------------------------------- ...... ^ hash() | clé K --------> code de hachage N = indice dans le tableau

Concrètement, une table de hachage ne peut pas être infinie et il est difficile de garantir que deux clés différentes auront deux codes de hachage différents. Pour cette raison, il peut arriver que plusieurs couples clé/valeur se retrouvent dans la même case du tableau. De façon à gérer ces collisions, chaque entrée du tableau stocke en fait une liste d'associations clés/valeurs secondaire. Comme présenté sur la figure ci-dessous, pour trouver la valeur associée à la clé k5, il faut d'abord calculer le code de hachage H de la clé (dans notre exemple, ce code vaut 7, la façon de calculer les codes de hachage est discuté dans l'exercice 1). Ensuite, l'entrée à laquelle se trouve la clé k5 est H modulo la taille du tableau (dans notre exemple, l'entrée est 2). Comme il peut y avoir des collisions lorsque plusieurs clés sont associées à cette entrée, l'entrée contient une liste d'association clés/valeurs. Il suffit alors de chercher k5 dans cette liste pour retrouver la valeur v5 associée à k5. [k6, v6] ^ | [k2, v2] [k5, v5] ^ ^ | | [k1, v1] [k3, v3] [k4, v4] [k7, v7] ^ ^ ^ ^ | | | | ---------------------------------------------- Table | | | | | | ---------------------------------------------- ^ | ---------------------- | Clé k5 => code hachage 7 => 7 mod taille tableau = 2 => cherche k5 dans la liste à l'entrée 2 => renvoie v5

Si le tableau a une taille suffisamment grande et si la probabilité de collision entre codes de hachage est faible, les listes référencées par la table contiennent au plus une unique entrée. L'algorithme met donc un temps constant, indépendant du nombre d'éléments se trouvant dans la table de hachage, pour trouver une valeur à partir d'une clé. Dans la plupart des mises en œuvre, on a toutefois des tailles de liste égales en moyenne à une racine nième du nombre d'éléments (où n est une constante dépendante de la mise en œuvre), ce qui offre des performances très satisfaisantes. Dans ce premier exercice, nous mettons en œuvre les clés (les identifiants de ville) et les valeurs (les positions GPS). La table de hachage que nous concevons dans les exercices suivants associera chaque identifiant de ville à une position. Après avoir créé le projet gps, créez une classe Main contenant la méthode statique main dans le package tsp.gps. Une clé est une instance de la classe CityId. Cette classe possède un unique champ privé de type chaîne de caractères nommé name qui identifie de façon unique une ville. Dans le package tsp.gps, créez la classe CityId avec son champ name. Ajoutez à cette classe :
  • un constructeur permettant d'initialiser le nom de la ville,
  • et une méthode String toString() renvoyant le nom de la ville.

Dans la méthode main créez une instance de CityId et vérifiez que la méthode toString() permet d'afficher correctement l'instance.
Ajoutez une classe nommée Location dans tsp.gps définissant les champs privés latitude et longitude de type double. Ajoutez à cette classe :
  • un constructeur permettant d'initialiser ces champs,
  • et une méthode toString() renvoyant la chaîne de caractères "lat, long", dans laquelle lat correspond à la latitude et long à la longitude.

Dans la méthode main créez une instance de Location et vérifiez que la méthode toString() permet d'afficher correctement l'instance.
La classe CityId va nous servir de clé. Il faut donc être capable de comparer deux instances de CityId pour savoir si elles sont égales. À cette question, nous nous occupons de savoir ce que signifie l'égalité entre CityId. Commencez par supprimer tout le code se trouvant dans la méthode main et copiez-collez le code suivant à la place : CityId evry1 = new CityId("Evry"); CityId evry2 = new CityId("Evry");

Ensuite, affichez le résultat de la comparaison de evry1 avec evry2 avec l'opérateur ==. Pour quelle raison l'opérateur d'égalité renvoie-t-il faux ? Car l'opérateur == effectue une comparaison par référence, c'est-à-dire qu'il compare la référence evry1 et evry2. Ces deux variables référençant deux objets différents, le résultat est faux.
Dans notre exercice, nous sommes intéressés par comparer le contenu des instances de CityId de façon à identifier que evry1 et evry2 sont bien deux identifiants pour la même ville. Cette comparaison des contenus s'appelle la comparaison par valeur, qui est à mettre en opposition à la comparaison par référence effectuée par l'opérateur ==. En effet, la comparaison par référence se cantonne à comparer les références de façon à savoir si elles référencent bien le même objet.

Techniquement, une comparaison par valeur indique si deux objets sont similaires dans un sens défini par le développeur. Dans notre cas, deux instances de CityId sont égales si elles possèdent des champs noms constitués des mêmes lettres. On pourrait imaginer ajouter d'autres champs non significatifs pour la comparaison, et il faudrait alors les ignorer lorsqu'on compare des CityId. Comme la comparaison par valeur dépend donc de la structure de donnée, Java ne fournit pas d'opérateur spécifique permettant d'effectuer une comparaison par valeur. À la place, la classe Object définit une méthode de comparaison par valeur boolean equals(Object o) générique qui peut donc être spécialisée par n'importe quelle classe puisque toutes les classes héritent de Object.

Ajoutez une méthode public boolean equals(Object o) à la classe CityId. Cette méthode doit déjà vérifier que o est bien du type CityId en utilisant l'opérateur Java instanceof. Ensuite, si c'est le cas, cette méthode doit sous-typer o en CityId et renvoyer vrai si les champs name de this et o sont égaux.

De la même façon qu'une comparaison par référence de nos CityId renvoie faux, une comparaison par référence de leur champ name peut aussi renvoyer faux si le contenu des chaînes des caractères sont les mêmes mais que les objets référencés sont différents. Pour cette raison, lorsque vous comparez le champ name de this avec celui de o, utilisez la méthode d'instance String.equals qui a été redéfinie dans la classe String afin d'effectuer une comparaison par valeur (techniquement, cette méthode vérifie que les caractères constituant les chaînes sont égaux).
Vérifiez que evry1.equals(evry2) renvoie vrai, que evry1.equals(new CityId("Paris")) renvoie faux et que evry1.equals("Evry") renvoie aussi faux. Comme expliqué précédemment, il faut être capable de calculer la clé de hachage d'une clé. Nous enrichissons donc la classe CityId de façon à calculer son code de hachage. La classe Object définit une méthode d'instance générique public int hashCode() dédiée au calcul de code de hachage. Nous vous proposons donc de spécialiser cette méthode dans CityId.

Comme code de hachage, nous pourrions renvoyer n'importe quelle valeur, pourvu que les codes de hachage de deux objets égaux dans le sens comparaison par valeur (on vous rappelle que dans notre cas, deux clés sont égales si elles ont les mêmes noms de villes) soient égaux. En effet, cet invariant est fondamental : si deux clés égales k1 et k2 avaient des codes de hachage h1 et h2 différents, la recherche de k2 dans l'entrée h2 du tableau de hachage ne permettrait pas de retrouver la clé k1 se trouvant à l'entrée h1.

De façon à assurer l'unicité du code de hachage de deux clés différentes, et de façon à assurer que les collisions de code de hachage sont rares, nous vous proposons de réutiliser la méthode d'instance hashCode() de la classe String (cette méthode effectue des additions et des opérations binaires à partir des numéros des caractères constituant la chaîne de caractères). Notre méthode d'instance CityId.hashCode() doit donc simplement renvoyer le résultat de l'appel à hashCode() sur le champ name d'une instance de CityId.

Dans votre méthode main, vérifiez que evry1 et evry2 ont bien le même code de hachage.
Avant de se lancer dans la mise en œuvre d'une table de hachage complète, nous commençons par gérer la liste permettant de stocker les clés qui entrent en collision dans la table de hachage. Cette liste est elle-même une table d'associations puisqu'elle associe aussi des clés et des valeurs.

Nous vous proposons de construire cette liste à partir d'une liste doublement chaînée circulaire. Dans cet exercice, nous concevons la liste doublement chaînée circulaire. Nous nous préoccupons de la transformer en table d'associations dans l'exercice suivant, et nous finissons par construire la table de hachage complète dans les deux exercices qui suivent.

Une liste doublement chaînée circulaire est une liste chaînée circulaire, c'est-à-dire que le dernier nœud référence le premier nœud. C'est aussi une liste doublement chaînée, c'est-à-dire qu'un nœud possède une référence avant (next) comme dans une liste chaînée classique, mais aussi une références arrière (prev) vers le nœud qui le précède dans la liste. Comparée à la liste simplement chaînée non circulaire que vous avez vue en CI3, la liste doublement chaînée circulaire rend le code de suppression d'un nœud beaucoup plus simple.

La figure ci-dessus présente une liste doublement chaînée circulaire de villes. Le premier nœud (en gris) s'appelle le nœud racine. Il représente un point d'entrée dans la liste. Les flèches pleines en bleu représentent les références vers l'avant (next) et les flèches rouge en pointillé représentent les références vers l'arrière (prev). Si on suit les références vers l'avant, on voit que la racine référence la première ville, ici Tours. Ensuite, une chaîne de ville permet d'atteindre la dernière ville, ici Bilbao. Enfin, la dernière ville référence la racine pour rendre la liste circulaire. De façon similaire, on peut parcourir la liste dans le sens inverse en suivant le chaînage prev. Commencez par créer un nouveau package nommé tsp.hashmap (sous Eclipse, File->New->Package). Ce package nous sert à stocker les classes qui modélisent les tables d'associations, alors que le package tsp.gps (voir exercice précédent) nous sert à stocker les classes de l'application associant des villes à des coordonnées GPS. Ajoutez une classe nommée ListMap au package tsp.hashmap. Cette classe associe des clés à des valeurs et doit donc être paramétrée par deux types génériques : le type K donne le type de la clé alors que le type V donne le type de la valeur. La classe ListMap représente un des nœuds de la liste doublement chaînée circulaire. Elle doit donc posséder les champs privés next, prev, key et value. Pour être précis, les champs de ListMap sont :
  • ListMap<K, V> next référence le nœud suivant de la liste,
  • ListMap<K, V> prev référence le nœud précédent de la liste,
  • K key référence la clé associée au nœud,
  • V value référence la valeur associée au nœud,
Ajoutez un constructeur à ListMap permettant d'initialiser un nœud de la liste chaînée. Ce constructeur doit prendre en argument une clé et une valeur et les affecter aux champs adéquats. Ce constructeur doit aussi initialiser les références next et prev de façon à ce que le nœud alloué soit une liste doublement chaînée circulaire constituée d'un unique nœud. La figure ci-dessous illustre cet état initial.

Ajoutez une méthode String toString() à la classe ListMap. Cette méthode doit renvoyer la chaîne de caractère (k, v), dans laquelle k est remplacé par l'appel à toString() sur la clé et v par l'appel à toString() sur la valeur. Dans la méthode main, allouez une instance de ListMap paramétrée de façon à associer des CityId à des Location. Initialisez cette instance avec le CityId et le Location que vous avez déjà créés à l'exercice précédent. Comme la classe ListMap n'est pas dans le même package que la classe Main, on vous rappelle que pour importer une classe X d'un package a.b.c, il faut mettre import a.b.c.X; dans l'entête du fichier Java.

Finalement, affichez sur le terminal cette instance de ListMap, et vérifiez que vous obtenez bien un affichage similaire à celui-ci : (Toulouse, 43.604652, 1.4442090000000007)
Nous écrivons maintenant une méthode permettant d'insérer un nœud dans une liste circulaire doublement chaînée. Pour le moment, nous ne nous soucions pas d'assurer l'unicité des clés, ce sera le sujet d'une prochaine question. Ajoutez une méthode d'instance append prenant en paramètre une clé et une valeur. Cette méthode insère un nœud associant la clé à la valeur passée en paramètre après le receveur de l'appel (this). La série de figure ci-dessous illustre l'algorithme que vous devez mettre en œuvre où node est le nouveau nœud à insérer dans la chaîne.
Avant insertion Première étape Seconde étape Troisième étape Quatrième étape
node.next = this.next node.prev = this this.next.prev = node this.next = node
Comme présenté dans la figure au début de l'exercice, une liste doublement chaînée circulaire possède une racine. Ce nœud racine est un faux nœud, c'est-à-dire qu'il ne stocke pas de clé ou de valeur. Il ne sert que de point d'entrée dans la liste, même quand la liste est vide. Il s'agit techniquement d'un nœud référençant la clé null et la valeur null.

De façon à préparer les tests suivants, commencez par supprimer tout le code qui se trouve dans la méthode main. À la place, créez un nœud racine nommé root et utilisez append pour ajouter au moins 3 villes avec des coordonnées quelconques. Si, lorsque vous lancez votre programme, Eclipse vous signale l'erreur NullPointerException, c'est que le code de append est incorrect et il faut que vous recommenciez la question f.
Ajoutez une méthode void display() à la classe ListMap permettant d'afficher les couples clé/valeur de chacun des nœuds de la liste. Cette méthode considère que le receveur de l'appel est une racine et n'affiche donc pas son contenu. En revanche, elle affiche le résultat de l'appel à toString() sur chacun des nœuds de la liste. Vérifiez que votre code est correct en appelant display sur la liste root que vous avez construite à la question précédente. Vous devriez obtenir un affichage similaire à celui-ci : List: (Bilbao, 43.2630126, -2.9349852000000283) (Panpelune, 42.812526, -1.645774500000016) (San Sebastien, 43.318334, -1.9812312999999904) (Bayonne, 43.492949, -1.4748409999999694) Pensez que si vous avez des erreurs, elles peuvent venir de display, mais aussi de append.

Pour vous guider, vous pouvez parcourir la liste en écrivant une boucle qui commence avec le premier nœud après la racine, qui suit les références next, et qui s'arrête quand la racine est atteinte.
Dans cet exercice, nous terminons notre mise en œuvre de la liste doublement chaînée circulaire de façon à la transformer en table d'associations. Ajoutez à la classe ListMap une méthode ListMap<K, V> lookupNode(K key) permettant de retrouver un nœud associé à la clé key dans la liste. Cette méthode doit parcourir la liste, un peu comme vous l'aviez fait dans la méthode display. Si pendant le parcours, vous trouvez un nœud avec un clé égale (dans le sens comparaison par valeur, c'est-à-dire en utilisant equals) au paramètre de la méthode, il faut renvoyer ce nœud, sinon, il faut renvoyer la valeur null.

Dans la méthode main, vérifiez que votre code est correct en essayant (i) de trouver le nœud associé à l'une de vos villes dans la liste root, et (ii) de trouver une ville qui n'y est pas.
Ajoutez une méthode V get(K key) renvoyant la valeur associée à la clé key si elle existe et null sinon. Cette méthode peut bien sûr appeler lookupNode pour retrouver le nœud associé à key. Ajoutez une méthode boolean remove(K key) permettant de supprimer une association et renvoyant vrai si et seulement si l'association existait avant l'appel. Cette méthode peut bien sûr appeler lookupNode pour retrouver le nœud associé à key. Dans la méthode main, supprimez l'une de vos villes et appelez display() pour vérifier que votre liste est correcte.

Pour supprimer un nœud N d'une liste doublement chaînée circulaire, il suffit que le prédécesseur de N joigne directement le suivant de N et réciproquement. Techniquement, il faut que le suivant du prédécesseur de N référence le suivant de N, et que le prédécesseur du suivant de N référence le prédécesseur de N.
Ajoutez une méthode boolean put(K key, V value) permettant d'ajouter l'association entre key et value. Si il n'existe pas d'association entre key et value, cette méthode doit créer une nouvelle association en appelant append et renvoyer vrai. Sinon, elle doit mettre à jour l'ancienne association en modifiant son champ valeur et renvoyer faux. Pensez que vous pouvez retrouver l'ancienne association, si elle existe, avec lookupNode. Afin de tester votre code, supprimez tout le code qui se trouve dans la méthode main. À la place, copiez-collez le code suivant : ListMap<CityId, Location> map = new ListMap<CityId, Location>(null, null); map.put(new CityId("Evry"), new Location(48.629828, 2.4417819999999892)); map.put(new CityId("Paris"), new Location(48.85661400000001, 2.3522219000000177)); map.put(new CityId("Le Mans"), new Location(48.00611000000001, 0.1995560000000296)); map.put(new CityId("Orléan"), new Location(47.902964, 1.9092510000000402)); map.put(new CityId("Angers"), new Location(47.478419, -0.5631660000000238)); map.put(new CityId("Tours"), new Location(47.39414399999999, 0.6848400000000083)); map.put(new CityId("Bourges"), new Location(47.081012, 2.398781999999983)); map.put(new CityId("Poitiers"), new Location(46.58022400000001, 0.34037499999999454)); map.put(new CityId("Limoges"), new Location(45.83361900000001, 1.2611050000000432)); map.put(new CityId("Angouleme"), new Location(45.648377, 0.15623690000006718)); map.put(new CityId("Bordeaux"), new Location(44.837789, -0.5791799999999512)); map.put(new CityId("Agen"), new Location(44.203142, 0.6163629999999785)); map.put(new CityId("Toulouse"), new Location(43.604652, 1.4442090000000007)); map.put(new CityId("Bayonne"), new Location(43.492949, -1.4748409999999694)); map.put(new CityId("Pau"), new Location(43.2951, -0.3707970000000387)); map.put(new CityId("San Sebastien"), new Location(43.318334, -1.9812312999999904)); map.put(new CityId("Panpelune"), new Location(42.812526, -1.645774500000016)); map.put(new CityId("Bilbao"), new Location(43.2630126, -2.9349852000000283)); map.display(); System.out.println(map.get(new CityId("Bilbao"))); map.remove(new CityId("Bilbao")); System.out.println(map.get(new CityId("Bilbao")));

L'exécution de ce test devrait vous générer un affichage similaire à celui-ci : List: (Bilbao, 43.2630126, -2.9349852000000283) (Panpelune, 42.812526, -1.645774500000016) (San Sebastien, 43.318334, -1.9812312999999904) (Pau, 43.2951, -0.3707970000000387) (Bayonne, 43.492949, -1.4748409999999694) (Toulouse, 43.604652, 1.4442090000000007) (Agen, 44.203142, 0.6163629999999785) (Bordeaux, 44.837789, -0.5791799999999512) (Angouleme, 45.648377, 0.15623690000006718) (Limoges, 45.83361900000001, 1.2611050000000432) (Poitiers, 46.58022400000001, 0.34037499999999454) (Bourges, 47.081012, 2.398781999999983) (Tours, 47.39414399999999, 0.6848400000000083) (Angers, 47.478419, -0.5631660000000238) (Orléan, 47.902964, 1.9092510000000402) (Le Mans, 48.00611000000001, 0.1995560000000296) (Paris, 48.85661400000001, 2.3522219000000177) (Evry, 48.629828, 2.4417819999999892) 43.2630126, -2.9349852000000283 null
Finalement, nous encapsulons de façon un peu plus satisfaisante les méthodes de ListMap. En effet, utiliser directement append de l'extérieur n'est pas recommandé. La méthode append permet d'ajouter manuellement des nœuds, et ne permet pas d'assurer qu'une clé est associée à une unique valeur, ce qui risquerait d'entraîner des erreurs chez les utilisateurs de votre table d'associations. Pour cette raison, nous vous suggérons de rendre la méthode append privée. Vous pouvez aussi rendre lookupNode privé car cette méthode n'a pas vocation à être utilisée de l'extérieur de la classe. Félicitations, vous venez de mettre en œuvre une structure de donnée connue pour être complexe !
Avant de mettre en œuvre les tables de hachages, nous abstrayons la notion de table d'associations sous la forme d'une interface. Dans le package tsp.hashmap, ajoutez une interface nommée Map paramétrée par le type K d'une clé et le type V d'une valeur. Ensuite, ajoutez les méthodes suivantes à l'interface :
  • boolean put(K key, V value) : crée une association et renvoie vrai si la clé n'avait aucune association auparavant,
  • V get(K key) : renvoie la valeur associée à key si elle existe et null sinon,
  • boolean remove(K key) : supprime l'association de key et renvoie vrai si elle existait,
  • void display() : affiche toutes les associations de la table d'associations sur le terminal.

Enfin, modifiez la déclaration de ListMap afin qu'elle mette en œuvre Map. Si le code de ListMap est correct, vous ne devriez rien avoir à faire d'autre puisque les méthodes de l'interface Map sont déjà mises en œuvre dans ListMap.
Maintenant que nous avons une interface générique de table d'associations, nous pouvons nous en servir dans la méthode main. Au début du main, remplacez la déclaration : ListMap<CityId, Location> map = new ListMap<CityId, Location>(null, null);

par Map<CityId, Location> map = new ListMap<CityId, Location>(null, null);

de façon à s'assurer que le code de main n'utilise que l'interface d'une liste d'associations et ne dépend pas des détails de mise en œuvre. Vérifiez que votre code s'exécute toujours correctement.
Maintenant que nous avons conçu toutes les classes et interfaces de base, nous pouvons enfin mettre en œuvre les tables de hachage. Techniquement, notre table de hachage est simplement un tableau de ListMap : les ListMap permettent de gérer les clés qui entrent en collision. Dans le package tsp.hashmap, ajoutez une classe nommée HashMap paramétrée par le type K d'une clé et le type V d'une valeur. Cette classe doit mettre en œuvre l'interface Map. Dans un premier temps, laissez les mise en œuvre des méthodes de Map vides :
  • put renvoie toujours faux,
  • get renvoie toujours null,
  • remove renvoie toujours faux,
  • display ne fait rien.
Modifiez le code de main afin d'allouer une instance de HashMap au lieu d'une instance de ListMap. Vous ne devriez avoir besoin que de modifier la ligne qui alloue la table d'associations. Vérifiez que vous pouvez toujours lancer votre application qui devrait vous produire l'affichage suivant : null null Une table de hachage est techniquement un tableau de Map dans lequel chaque élément référence une instance de ListMap. Ajoutez à HashMap un champ table référençant un tableau de Map. Dans le constructeur de HashMap, initialisez ce champ avec un tableau de 5 Map, puis initialisez chacune des entrées de ce tableau en allouant un nouveau ListMap pour chaque entrée. Pour mettre en œuvre put, get et remove, nous aurons besoin de connaître le ListMap dans lequel se trouve une clé. Par exemple, que ce soit pour ajouter une clé, trouver la valeur associée à une clé ou supprimer une clé, nous avons besoin de savoir que le ListMap dans lequel se trouve la clé k5 est à l'indice 2 dans la figure présentée au début de l'exercice. Écrivez une méthode intermédiaire Map getList(K key) renvoyant une référence vers le ListMap dans lequel la clé key devrait se trouver. En détail, getList doit :
  • Calculer le code de hachage H de key en appelant hashCode().
  • Effectuer un modulo de H avec la taille du tableau de hachage (table.length). Le résultat r de ce modulo devrait donner l'indice du TableMap dans le tableau table dans lequel key doit se trouver. Toutefois, en Java, le modulo d'un nombre négatif reste négatif et ne peut pas directement être utilisé comme indice dans table. Si ce modulo est négatif, il faut que vous y ajoutiez table.length pour le rendre positif.
  • Renvoyer le ListMap se trouvant à l'indice r de table.
Nous pouvons maintenant mettre en œuvre put, get et remove. Chacune de ces méthodes doit appeler getList pour retrouver le ListMap associé à la clé passée en paramètre, puis déléguer l'appel à la méthode adéquate de ListMap. Complétez le code de HashMap.display. Il suffit d'invoquer display sur chaque élément du tableau. Vérifiez que l'affichage produit est similaire à celui de l'exercice 3. Félicitations, vous venez d'écrire une superbe table de hachage réutilisable ! Le code que vous avez écrit est assez similaire à celui fourni par Oracle dans sa machine virtuelle Java. Si vous voulez approfondir le sujet, n'hésitez pas à redimensionner dynamiquement le tableau lorsque le nombre de collision devient trop grand (la bibliothèque Java redimensionne la table lorsqu'il existe des listes chaînées qui ont une taille supérieure à 70% de la taille du tableau).