Série 5 – Tables associatives
Cette série est la cinquième et dernière du micro-projet consacré aux collections. Comme pour les séries précédentes vous placerez tout votre code dans le paquetage ch.epfl.collections.
Le but de cette série est de mettre la touche finale à votre bibliothèque de collections en y ajoutant deux mises en œuvre des tables associatives. Ces deux mises en œuvre doivent implémenter l'interface Map que nous mettons à votre disposition.
Tables associatives par hachage
Commencez par écrire la classe générique HashMap, qui met en œuvre une table associative au moyen d'une table de hachage.
La manière la plus simple d'obtenir la classe HashMap est probablement de copier la classe HashSet — soit votre version, soit celle de notre corrigé — puis de la transformer progressivement pour qu'elle mette en œuvre une table associative plutôt qu'un ensemble. Ce travail peut être grandement simplifié par une utilisation judicieuse des fonctions de refactorisation d'Eclipse. Par exemple, le paramètre de type E de la classe peut ainsi être renommé facilement en K (étant donné que les clefs des tables associatives correspondent aux éléments des ensembles). Il en va de même du paramètre de type de la classe imbriquée Node, qui peut quant-à-elle être renommée en Entry. Et ainsi de suite…
Une fois la classe HashMap écrite, il convient comme d'habitude de la tester au moyen de JUnit. Pour cela, vous pouvez soit adapter les tests sur les ensembles, soit en créer de nouveaux. Pensez à vérifier que la méthode put se comporte comme elle devrait lorsqu'on l'appelle avec une clef qui existe déjà, c-à-d qu'elle met à jour la valeur associée à cette clef.
Tables associatives par arbre de recherche
Une fois la classe HashMap terminée, procédez de manière similaire pour adapter la classe TreeSet afin d'en faire une classe TreeMap mettant en œuvre les tables associatives au moyen d'un arbre binaire de recherche.
Comme d'habitude, testez votre classe dès son écriture terminée.