| 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 |
Voici tout d'abord une terminologie nécessaire pour comprendre les mécanismes mis en jeu :
Capacité : Le nombre de seaux dans la table.
Capacité initiale : Le nombre de seaux dans la table quand celle-ci est créée. Les HashMap et les HashSet proposent des constructeurs qui permettent de spécifier la capacité initiale.
Taille : Le nombre courant d'entrées dans la table.
Facteur de charge : taille/capacité. Un facteur de charge de 0 correspond à une table vide, 0.5 correspond à une table à moitié pleine, etc. Une table faiblement chargée aura peu de collisions et sera donc optimale pour les insertions et les recherches (mais ralentira le processus de parcours avec un itérateur). HashMap et HashSet proposent des constructeurs qui permettent de spécifier un facteur de charge, ce qui veut dire que lorsque ce facteur de charge est atteint le conteneur augmentera automatiquement sa capacité (le nombre de seaux) en la doublant d'un coup, et redistribuera les objets existants dans le nouvel ensemble de seaux (c'est ce qu'on appelle le rehachage).
Le facteur de charge par défaut utilisé par HashMap est 0.75 (il ne se rehache pas avant que la table ne soit aux ¾ pleine). Cette valeur est un bon compromis entre les performances et le coût en espace. Un facteur de charge plus élevé réduit l'espace requis par une table mais augmente le coût d'une recherche, ce qui est important parce que les recherches sont les opérations les plus courantes (incluant les appels get() et put()).
Si un HashMap est destiné à recevoir beaucoup d'entrées, le créer avec une grosse capacité initiale permettra d'éviter le surcoût du rehachage automatique.
Maintenant que nous avons vu les processus impliqués dans le fonctionnement d'un HashMap, les problèmes rencontrés dans l'écriture d'une méthode hashCode() prennent tout leur sens.
Tout d'abord, on ne contrôle pas la valeur réellement utilisée pour indexer le seau dans le tableau. Celle-ci est dépendante de la capacité de l'objet HashMap, et cette capacité change suivant la taille et la charge du conteneur. La valeur renvoyée par la méthode hashCode() est simplement utilisée pour calculer l'index du seau (dans SimpleHashMap le calcul se résume à un modulo de la taille du tableau de seaux).
Le facteur le plus important lors de la création d'une méthode hashCode() est qu'elle doit toujours renvoyer la même valeur pour un objet particulier, quel que soit le moment où hashCode() est appelée. Si on a un objet dont la méthode hashCode() renvoie une valeur lors d'un put() dans un HashMap, et une autre durant un appel à get(), on sera incapable de retrouver cet objet. Si la méthode hashCode() s'appuie sur des données modifiables dans l'objet, l'utilisateur doit alors être prévenu que changer ces données produira une clef différente en générant un code de hachage différent.
De plus, on ne veut pas non plus générer un code de hachage qui soit basé uniquement sur des informations uniques spécifiques à l'instance de l'objet - en particulier, la valeur de this est une mauvaise idée pour un code de hachage, puisqu'on ne peut générer une nouvelle clef identique à celle utilisée pour stocker la paire originale clef-valeur. C'est le problème que nous avons rencontré dans SpringDetector.java parce que l'implémentation par défaut de hashCode()utilise l'adresse de l'objet. Il faut donc utiliser des informations de l'objet qui identifient l'objet d'une façon sensée.
Un exemple en est trouvé dans la classe String. Les Strings ont cette caractéristique spéciale : si un programme utilise plusieurs objets String contenant la même séquence de caractères, alors ces objets String pointent tous vers la même zone de mémoire (ce mécanisme est décrit dans l'annexe A). Il semble donc sensé que le code de hachage produit par deux instances distinctes de new String("hello") soit identique. On peut le vérifier avec ce petit programme :
Pour que ceci fonctionne, le code de hachage de String doit être basé sur le contenu de la String.
Pour qu'un code de hachage soit efficace, il faut donc qu'il soit rapide et chargé de sens : c'est donc une valeur basée sur le contenu de l'objet. Rappelons que cette valeur n'a pas à être unique - mieux vaut se pencher sur la vitesse que sur l'unicité - mais l'identité d'un objet doit être complètement résolue entre hashCode() et equals().
Parce qu'un code de hachage est traité avant de produire un index de seau, la plage de valeurs n'est pas importante ; il suffit de générer un int.
Enfin, il existe un autre facteur : une méthode hashCode() bien conçue doit renvoyer des valeurs bien distribuées. Si les valeurs tendent à se regrouper, alors les HashMaps et les HashSets seront plus chargés dans certaines parties et donc moins rapides que ce qu'ils pourraient être avec une fonction de hachage mieux répartie.
Voici un exemple qui respecte ces règles de base :
CountedString inclut une String et un id représentant le nombre d'objets CountedString contenant une String identique. Le compte est réalisé dans le constructeur en parcourant la static ArrayList où toutes les Strings sont stockées.
Les méthodes hashCode() et equals() renvoient des résultats basés sur les deux champs ; si elles étaient basées juste sur la String ou sur l'id, il y aurait eu des doublons pour des valeurs distinctes.
Notez comme la fonction de hachage est simple : le code de hachage de la String multiplié par l'id. Généralement, la qualité et la rapidité d'une fonction de hachage est inversement proportionnelle à sa taille.
Dans main(), un ensemble d'objets CountedString est créé, en utilisant la même String pour montrer que les doublons créent des valeurs uniques grâce au compteur id. Le HashMap est affiché afin de voir son organisation interne (aucun ordre n'est discernable) ; chaque clef est alors recherchée individuellement pour démontrer que le mécanisme de recherche fonctionne correctement.
La bibliothèque java.lang.ref contient un ensemble de classes qui permettent une plus grande flexibilité dans le nettoyage des objets, et qui se révèlent particulièrement pratiques lorsqu'on a de gros objets qui peuvent saturer la mémoire. Il y a trois classes dérivées de la classe abstraite Reference : SoftReference, WeakReference et PhantomReference. Chacune d'entre elles fournit un niveau différent d'abstraction au ramasse miettes, si l'objet en question n'est accessible qu'à travers un de ces objets Reference.
Si un objet est accessible cela veut dire que l'objet peut être trouvé quelque part dans le programme. Ceci peut vouloir dire qu'on a une référence ordinaire sur la pile qui pointe directement sur l'objet, mais on peut aussi avoir une référence sur un objet qui possède une référence sur l'objet en question ; il peut y avoir de nombreux liens intermédiaires. Si un objet est accessible, le ramasse miettes ne peut pas le nettoyer parce qu'il est toujours utilisé par le programme. Si un objet n'est pas accessible, le programme ne dispose d'aucun moyen pour y accéder et on peut donc nettoyer cet objet tranquillement.
On utilise des objets Reference quand on veut continuer à stocker une référence sur cet objet - on veut être capable d'atteindre cet objet - mais on veut aussi permettre au ramasse miettes de nettoyer cet objet. Il s'agit donc d'un moyen permettant de continuer à utiliser l'objet, mais si la saturation de la mémoire est imminente, on permet que cet objet soit nettoyé.
Un objet Reference sert donc d'intermédiaire entre le programme et la référence ordinaire, et aucune référence ordinaire sur cet objet ne doit exister (mis à part celles encapsulées dans les objets Reference). Si le ramasse miette découvre qu'un objet est accessible à travers une référence ordinaire, il ne nettoiera pas cet objet.
Dans l'ordre SoftReference, WeakReference et PhantomReference, chacune d'entre elles est « plus faible » que la précédente, et correspond à un niveau différent d'accessibilité. Les références douces (SoftReferences) permettent d'implémenter des caches concernés par les problèmes de mémoire. Les références faibles (WeakReferences) sont destinées à implémenter des « mappages canoniques » - où des instances d'objets peuvent être utilisées simultanément dans différents endroits du programme, pour économiser le stockage - qui n'empêchent pas leurs clefs (ou valeurs) d'être nettoyées. Les références fantômes (PhantomReferences) permettent d'organiser les actions de nettoyage pre-mortem d'une manière plus flexible que ce qui est possible avec le mécanisme de finalisation de Java.
Pour les SoftReferences et les WeakReferences, on peut choisir de les stocker dans une ReferenceQueue (le dispositif utilisé pour les actions de nettoyage pre-mortem) ou non, mais une PhantomReference ne peut être créée que dans une ReferenceQueue. En voici la démonstration :
Quand on lance ce programme (vous voudrez probablement piper la sortie à travers un utilitaire « more » afin de pouvoir l'observer page par page), on verra que les objets sont récupérés par le ramasse miettes, même si on a toujours accès à eux à travers les objets Reference (pour obtenir la référence réelle sur l'objet, il faut utilise la méthode get()). On notera aussi que ReferenceQueue renvoie toujours une Reference contenant un objet null. Pour utiliser les références, on peut dériver la classe Reference particulière qui nous intéresse et ajouter des méthodes au nouveau type de Reference.
La bibliothèque de conteneurs propose une Map spéciale pour stocker les références faibles : le WeakHashMap. Cette classe est conçue pour faciliter la création de mappages canoniques. Dans de tels mappages, on économise sur le stockage en ne créant qu'une instance d'une valeur particulière. Quand le programme a besoin de cette valeur, il recherche l'objet existant dans le mappage et l'utilise (plutôt que d'en créer un complètement nouveau). Le mappage peut créer les valeurs comme partie de son initialisation, mais il est plus courant que les valeurs soient créées à la demande.
Puisqu'il s'agit d'une technique permettant d'économiser sur le stockage, il est très pratique que le WeakHashMap autorise le ramasse miettes à nettoyer automatiquement les clefs et les valeurs. Aucune opération particulière n'est nécessitée sur les clefs et les valeurs qu'on veut placer dans le WeakHashMap ; ils sont automatiquement encapsulés dans des WeakReferences par le WeakHashMap. Le déclenchement qui autorise le nettoyage survient lorsque la clef n'est plus utilisée, ainsi que démontré dans cet exemple :
La classe Key doit fournir les méthodes hashCode() et equals() puisqu'elle est utilisée comme clef dans une structure de données hachée, comme décrit précédemment dans ce chapitre.
Quand on lance le programme, on s'aperçoit que le ramasse miettes évite une clef sur trois, parce qu'une référence ordinaire sur cette clef a aussi été placée dans le tableau keys et donc ces objets ne peuvent être nettoyés.
Nous pouvons maintenant démontrer la vraie puissance d'un Iterator : la capacité de séparer l'opération de parcourir une séquence de la structure sous-jacente de cette séquence. Dans l'exemple suivant, la classe PrintData utilise un Iterator pour se déplacer à travers une séquence et appelle la méthode toString() pour chaque objet. Deux types de conteneurs différents sont créés - une ArrayList et un HashMap - et remplis, respectivement, avec des objets Mouse et Hamster (ces classes ont été définies précédemment dans ce chapitre). Parce qu'un Iterator cache la structure sous-jacente du conteneur associé, PrintData ne se soucie pas du type de conteneur dont l'Iterator provient :
