| Penser en Java 2nde édition | - | Sommaire | Préface | Avant-propos | Chapitre : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | Annexe : A B C D | Tables des matières | - | Thinking in Java |
Si la clef n'a pas déjà été stockée, la méthode put() insèrera une nouvelle paire clef - valeur dans le HashMap. Puisque Counter initialise automatiquement sa variable i à 1 lorsqu'elle est créée, cela indique une première occurence de ce nombre aléatoire particulier.
Pour afficher le HashMap, il est simplement imprimé. La méthode toString() de HashMap parcourt toutes les paires clef - valeur et appelle toString() pour chacune d'entre elles. La méthode Integer.toString() est prédéfinie, et on peut voir la méthode toString() de la classe Counter. La sortie du programme (après l'insertion de quelques retours chariot) ressemble à :
On peut s'interroger sur la nécessité d'une classe Counter, qui ne semble même pas avoir les fonctionnalités de la classe d'encapsulation Integer. Pourquoi ne pas utiliser un int ou un Integer ? On ne peut utiliser un int puisque les conteneurs ne peuvent stocker que des références d'Object. On pourrait alors être tenté de se tourner vers les classes Java d'encapsulation des types primitifs. Cependant, ces classes ne permettent que de stocker une valeur initiale et de lire cette valeur. C'est à dire qu'il n'existe aucun moyen de changer cette valeur une fois qu'un objet d'encapsulation a été créé. Cela rend la classe Integer inutile pour résoudre notre problème, et nous force à créer une nouvelle classe qui statisfait l'ensemble de nos besoins.
Une SortedMap (dont TreeMap est l'unique représentant) garantit que ses éléments seront stockés triés selon leur clef, ce qui permet de proposer de nouvelles fonctionnalités grâce aux méthodes supplémentaires de l'interface SortedMap suivantes :
Comparator comparator() : Renvoie le Comparator utilisé pour cette Map, ou null dans le cas d'un tri naturel.
Object firstKey() : Renvoie la plus petite clef.
Object lastKey() : Renvoie la plus grande clef.
SortedMap subMap(fromKey, toKey) : Renvoie une vue de la Map contenant les paires dont les clefs vont de fromKey inclus à toKey exclu.
SortedMap headMap(toKey) : Renvoie une vue de la Map contenant les paires dont la clef est inférieure à toKey.
SortedMap tailMap(fromKey) : Renvoie une vue de la Map contenant les paires dont la clef est supérieure ou égale à fromKey.
Dans l'exemple précédent, une classe de la bibliothèque standard (Integer) était utilisée comme clef pour le HashMap. Cela ne pose pas de problèmes car elle dispose de tout ce qu'il faut pour fonctionner correctement comme une clef. Mais il existe un point d'achoppement classique avec les HashMaps lorsqu'on crée une classe destinée à être utilisée comme clef. Considérons par exemple un système de prévision météorologique qui associe des objets Groundhog à des objets Prediction. Cela semble relativement simple : il suffit de créer deux classes, et d'utiliser Groundhog comme clef et Prediction comme valeur :
Chaque Groundhog se voit attribuer un numéro d'identité, afin de pouvoir récupérer une Prediction dans le HashMap en disant « Donne-moi la Prediction associée au Groundhog numéro 3 ». La classe Prediction contient un boolean initialisé en utilisant Math.random(), et une méthode toString() pour en interpréter la valeur. Dans main(), un HashMap est rempli avec des Groundhogs et leurs Predictions associées. Le HashMap est affiché afin de voir qu'il a été correctement rempli. Un Groundhog avec une identité de 3 est alors utilisé comme clef pour extraire la prédiction du Groundhog numéro 3 (qui doit être dans le HashMap).
Tout ceci semble très simple, mais ne marche pas. Le problème vient du fait que Groundhog hérite de la classe de base Object (ce qui est le comportement par défaut si aucune superclasse n'est précisée ; toutes les classes dérivent donc en fin de compte de la classe Object). C'est donc la méthode hashCode() de Object qui est utilisée pour générer le code de hachage pour chaque objet, et par défaut, celle-ci renvoie juste l'adresse de cet objet. La première instance de Groundhog(3) ne renvoie donc pas le même code de hachage que celui de la seconde instance de Groundhog(3) que nous avons tenté d'utiliser comme clef d'extraction.
On pourrait penser qu'il suffit de redéfinir hashCode(). Mais ceci ne fonctionnera toujours pas tant qu'on n'aura pas aussi redéfini la méthode equals() qui fait aussi partie de la classe Object. Cette méthode est utilisée par le HashMap lorsqu'il essaie de déterminer si la clef est égale à l'une des autres clefs de la table. Et la méthode par défaut Object.equals() compare simplement les adresses des objets, ce qui fait qu'un objet Groundhog(3) est différent d'un autre Groundhog(3).
Pour utiliser un nouveau type comme clef dans un HashMap, il faut donc redéfinir les deux méthodes hashCode() et equals(), comme le montre la solution suivante :
Notez que cet exemple utilise la classe Prediction de l'exemple précédent, donc SpringDetector.java doit déjà avoir été compilé ou vous aurez une erreur lorsque vous tenterez de compiler SpringDetector2.java.
Groundhog2.hashCode() renvoie le numéro de marmotte comme identifiant. Dans cet exemple, le programmeur doit s'assurer que deux marmottes ne portent pas le même identifiant. La méthode hashCode() n'est pas obligée de renvoyer un identifiant unique (vous comprendrez mieux ceci plus tard dans ce chapitre), mais la méthode equals() doit être capable de déterminer si deux objets sont strictement équivalents.
Bien que la méthode equals() semble ne vérifier que si l'argument est bien une instance de Groundhog2 (en utilisant le mot-clef instanceof, expliqué plus en détails dans le Chapitre 12), instanceof effectue en fait implicitement un deuxième contrôle puisqu'il renvoie false si l'argument de gauche est null. En assumant que le contrôle de type s'est bien passé, la comparaison est basée sur les ghNumbers des instances. Et cette fois, lorsqu'on lance le programme, on peut voir qu'il produit le résultat attendu.
On rencontre les mêmes problèmes quand on crée un nouveau type destiné à être stocké dans un HashSet ou utilisé comme clef dans un HashMap.
L'exemple précédent n'est que le début de la solution complète et correcte de ce problème. Il montre que la structure de données hachée (HashSet ou HashMap) ne sera pas capable de gérer correctement les objets clef si on ne redéfinit pas les méthodes hashCode() et equals() pour ces objets. Cependant, pour fournir une solution propre au problème, il faut comprendre ce qui se passe derrière la structure de données hachée.
Pour cela, il faut tout d'abord comprendre le pourquoi du hachage : on veut extraire un objet associé à un autre objet. Mais il est aussi possible d'accomplir ceci avec un TreeSet ou un TreeMap. Il est même possible d'implémenter sa propre Map. Pour cela, il nous faut fournir une méthode Map.entrySet() qui renvoie un ensemble d'objets Map.Entry. MPair sera définie comme le nouveau type de Map.Entry. Afin qu'il puisse être placé dans un TreeSet il doit implémenter equals() et être Comparable :
Notez que les comparaisons ne s'effectuent que sur les clefs, les valeurs dupliquées sont donc parfaitement légales.
L'exemple suivant impémente une Map en utilisant une paire d'ArrayLists :
La méthode put() stocke simplement les clefs et les valeurs dans les ArrayLists correspondantes. Dans main(), une SlowMap est remplie et imprimée pour montrer qu'elle fonctionne.
Ceci montre qu'il n'est pas difficile de produire un nouveau type de Map. Mais comme son nom le suggère, une SlowMap n'est pas très rapide, et on ne l'utilisera probablement pas si on dispose d'une autre alternative. Le problème se trouve dans la recherche de la clef : comme elles sont stockées sans aucun ordre, une recherche linéaire est effectuée, ce qui constitue la manière la plus lente de rechercher un item particulier.
Tout l'intérêt du hachage réside dans la vitesse : le hachage permet d'effectuer la recherche rapidement. Puisque le goulot d'étranglement est la recherche de la clef, une des solution du problème serait de garder les clefs triées et d'utiliser ensuite Collections.binarySearch() pour réaliser la recherche (un exercice à la fin du chapitre vous mènera le long de ce processus).
Le hachage va encore plus loin en spécifiant que tout ce qu'on a besoin de faire est de stocker la clef quelque part afin de pouvoir la retrouver rapidement. Comme on l'a déjà vu dans ce chapitre, la structure la plus efficace pour stocker un ensemble d'éléments est un tableau, c'est donc ce que nous utiliserons pour stocker les informations des clefs (notez bien que j'ai dit : « information des clefs » et non les clefs elles-mêmes). Nous avons aussi vu dans ce chapitre qu'un tableau, une fois alloué, ne peut être redimensionné, nous nous heurtons donc à un autre problème : nous voulons être capable de stocker un nombre quelconque de valeurs dans la Map, mais comment cela est-ce possible si le nombre de clefs est fixé par la taille du tableau ?
Tout simplement, le tableau n'est pas destiné à stocker les clefs. Un nombre dérivé de l'objet clef servira d'index dans le tableau. Ce nombre est le code de hachage, renvoyé par la méthode hashCode() (dans le jargon informatique, on parle de fonction de hachage) définie dans la classe Object et éventuellement redéfinie dans un nouveau type. Pour résoudre le problème du tableau de taille fixe, plus d'une clef peut produire le même index ; autrement dit, les collisions sont autorisées. Et de ce fait, la taille du tableau importe peu puisque chaque objet clef atterira quelque part dans ce tableau.
Le processus de recherche d'une valeur débute donc par le calcul du code de hachage, qu'on utilise pour indexer le tableau. Si on peut garantir qu'il n'y a pas eu de collisions (ce qui est possible si on a un nombre fixé de valeurs), alors on dispose d'une fonction de hachage parfaite, mais il s'agit d'un cas spécial. Dans les autres cas, les collisions sont gérées par un chaînage externe : le tableau ne pointe pas directement sur une valeur, mais sur une liste de valeurs. Ces valeurs sont alors parcourues de façon linéaire en utilisant la méthode equals(). Bien sûr, cet aspect de la recherche est plus lent, mais si la fonction de hachage est correctement écrite, il n'y aura que quelques valeurs au plus dans chaque emplacement. Et donc au lieu de parcourir toute la liste pour trouver une valeur, on saute directement dans une cellule où seules quelques entrées devront être comparées pour trouver la valeur. Cette aproche est bien plus efficace, ce qui explique pourquoi un HashMap est si rapide.
Connaissant les bases du hachage, il est possible d'implémenter une Map simple hachée :
Comme on appelle souvent seaux les « emplacements » d'une table de hachage, le tableau représentant la table est appelé bucket. Pour s'assurer d'une distribution la plus régulière possible, le nombre de seaux est typiquement un nombre premier. Notez qu'il s'agit d'un tableau de LinkedLists, qui permet de gérer automatiquement les collisions - chaque nouvel item est simplement ajouté à la fin de la liste.
La valeur de retour de put() est null ou l'ancienne valeur associée à la clef si la celle-ci était présente dans la liste. La valeur de retour est result, qui est initialisée à null, mais se voit assigner une clef si celle-ci est découverte dans la liste.
Les deux méthodes put() et get() commencent par appeler la méthode hashCode() de l'objet clef, dont le résultat est forcé à un nombre positif. Il est alors forcé dans la plage du tableau via l'opérateur modulo et la taille du tableau. Si l'emplacement est null, cela veut dire qu'aucun élément ne hache à cette localisation, et donc une nouvelle LinkedList est créée pour contenir l'objet qui vient de le faire. Sinon, le processus normal est de parcourir la liste pour voir s'il existe un doublon, et si c'est le cas, l'ancienne valeur est stockée dans result et la nouvelle valeur remplace l'ancienne. Le flag found permet de savoir si une ancienne paire clef - valeur a été trouvée, et dans le cas contraire, une nouvelle paire est ajoutée à la fin de la liste.
Le code de get() est similaire à celui de put(), en plus simple. L'index dans le tableau bucket est calculé, et si une LinkedList existe elle est parcourue pour trouver une concordance.
entrySet() doit trouver et parcourir toutes les listes, ajoutant tous les éléments dans le Set résultat. Une fois cette méthode fournie, la Map peut être testée en la remplissant avec des valeurs et en les imprimant.
