Hashtables

21 juin 2002

Q: Lorsque j'utilise un objet comme clé dans une table de hachage, que dois-je remplacer dans la classe Object et pourquoi?

R: Lorsque vous créez votre propre objet clé à utiliser dans a Hashtable, vous devez remplacer les méthodes Object.equals()et Object.hashCode()car il Hashtableutilise une combinaison des méthodes clé hashCode()et equals()pour stocker et récupérer rapidement ses entrées. C'est également une règle générale que lorsque vous remplacez equals(), vous remplacez toujours hashCode().

En savoir plus sur pourquoi

Une explication un peu plus approfondie vous aidera à comprendre Hashtablele mécanisme de stockage et de récupération. A Hashtablecontient en interne des compartiments dans lesquels il stocke les paires clé / valeur. Le Hashtableutilise le hashcode de la clé pour déterminer à quel compartiment la paire clé / valeur doit mapper.

La figure 1 montre a Hashtableet ses godets. Lorsque vous transmettez une clé / valeur au Hashtable, il interroge le hashcode de la clé. Le Hashtableutilise ce code pour déterminer le compartiment dans lequel placer la clé / valeur. Ainsi, par exemple, si le hashcode est égal à zéro, le Hashtableplace la valeur dans le Bucket 0. De même, si le hashcode est deux, le Hashtableplace la valeur dans le Bucket 2. (Ceci est un exemple simpliste; Hashtableil massera le hashcode en premier afin que le Hashtablen'essaye pas d'insérer la valeur en dehors du compartiment.)

En utilisant le hashcode de cette manière, le Hashtablepeut également déterminer rapidement dans quel compartiment il a placé la valeur lorsque vous essayez de la récupérer.

Les Hashcodes ne représentent cependant que la moitié de l'image. Le hashcode indique uniquement Hashtabledans quel compartiment déposer la clé / valeur. Parfois, cependant, plusieurs objets peuvent mapper vers le même compartiment, un événement appelé collision. En Java, le Hashtablerépond à une collision en plaçant plusieurs valeurs dans le même compartiment (d'autres implémentations peuvent gérer les collisions différemment). La figure 2 montre à quoi Hashtablepourrait ressembler un après quelques collisions.

Imaginez maintenant que vous appelez get()avec une clé Hashtablemappée sur le compartiment 0. Le devra maintenant effectuer une recherche séquentielle dans les paires clé / valeur du compartiment 0 pour trouver la valeur demandée. Pour effectuer cette recherche, le Hashtableexécute les étapes suivantes:

  1. Interroger le hashcode de la clé
  2. Récupérer la liste des clés / valeurs résidant dans le compartiment donné par le hashcode
  3. Parcourez chaque entrée de manière séquentielle jusqu'à ce qu'une clé égale à la clé transmise get()soit trouvée

Une longue réponse à une courte question que je connais, mais ça empire. Remplacer correctement equals()et hashCode()est un exercice non trivial. Vous devez faire très attention pour garantir les contrats des deux méthodes.

Lors de la mise en œuvre de equals ()

Selon equals()Javadoc, la méthode doit être conforme aux règles suivantes:

"La equals()méthode implémente une relation d'équivalence:
  • C'est réflexif: pour toute valeur de référence x, x.equals(x)doit retourner true
  • Il est symétrique: pour toutes les valeurs de référence x et y, x.equals(y)doit retourner vrai si et seulement si y.equals(x)renvoie vrai
  • Il est transitif: pour toutes les valeurs de référence x, y et z, si x.equals(y)retourne true et y.equals(z)retourne true, alors x.equals(z)doit retourner true
  • Il est cohérent: pour toutes les valeurs de référence x et y, plusieurs invocations x.equals(y)retournent systématiquement true ou systématiquement false, à condition qu'aucune information utilisée dans les comparaisons égales sur l'objet ne soit modifiée
  • Pour toute valeur de référence x non nulle, x.equals(null)doit renvoyer false "

Dans Effective Java, Joshua Bloch propose une recette en cinq étapes pour écrire une equals()méthode efficace . Voici la recette sous forme de code:

classe publique EffectiveEquals {private int valueA; private int valueB; . . . public boolean equals (Object o) {if (this == o) {// Étape 1: Effectuer un test == return true; } if (! (o instanceof EffectiveEquals)) {// Étape 2: Instance de vérification return false; } EffectiveEquals ee = (EffectiveEquals) o; // Étape 3: Cast argument // Étape 4: Pour chaque champ important, vérifiez s'ils sont égaux // Pour les primitives, utilisez == // Pour les objets, utilisez equals () mais assurez-vous de // gérer également la casse nulle premier retour ee.valueA == valeurA && ee.valueB == valeurB; }. . . }

Remarque: vous n'avez pas besoin d'effectuer une vérification nulle car elle null instanceof EffectiveEqualssera évaluée à false.

Enfin, pour l'étape 5, revenez au equals()contrat de et demandez-vous si la equals()méthode est réflexive, symétrique et transitive. Sinon, corrigez-le!

Sur l'implémentation de hashCode ()

Pour hashCode()le contrat général, le Javadoc dit:

  • "Chaque fois qu'elle est invoquée sur le même objet plus d'une fois lors de l'exécution d'une application Java, la hashCode()méthode doit systématiquement renvoyer le même entier, à condition qu'aucune information utilisée dans les comparaisons égales sur l'objet ne soit modifiée. Cet entier n'a pas besoin de rester cohérent à partir d'un exécution d'une application à une autre exécution de la même application.
  • Si deux objets sont égaux selon la equals(Object)méthode, l'appel de la hashCode()méthode sur chacun des deux objets doit produire le même résultat entier.
  • Il n'est pas nécessaire que si deux objets sont inégaux selon la equals(java.lang.Objectméthode, l'appel de la hashCode()méthode sur chacun des deux objets doit produire des résultats entiers distincts. Cependant, le programmeur doit être conscient que la production de résultats entiers distincts pour des objets inégaux peut améliorer les performances des tables de hachage. "

Créer une hashCode()méthode qui fonctionne correctement s'avère difficile; cela devient encore plus difficile si l'objet en question n'est pas immuable. Vous pouvez calculer un hashcode pour un objet donné de plusieurs manières. La méthode la plus efficace base le nombre sur les champs de l'objet. De plus, vous pouvez combiner ces valeurs de différentes manières. Voici deux approches populaires:

  • Vous pouvez transformer les champs de l'objet en une chaîne, concaténer les chaînes et renvoyer le hashcode résultant
  • Vous pouvez ajouter le hashcode de chaque champ et renvoyer le résultat

S'il existe d'autres approches plus approfondies, les deux approches susmentionnées s'avèrent les plus faciles à comprendre et à mettre en œuvre.

Tony Sintes est un consultant indépendant et fondateur de First Class Consulting, une société de conseil spécialisée dans la mise en relation de systèmes d'entreprise disparates et la formation. En dehors de First Class Consulting, Tony est un écrivain indépendant actif, ainsi que l'auteur de Sams Teach Yourself Object-Oriented Programming in 21 Days (Sams, 2001; ISBN: 0672321092).

En savoir plus sur ce sujet

  • Pour le Javadoc Hashtable, accédez à

    //java.sun.com/j2se/1.4/docs/api/java/util/Hashtable.html

  • "Implémentation de equals () et hashCode ()" de Vipan Singla fournit une discussion approfondie sur le remplacement des méthodes equals () et hashCode ()

    //www.vipan.com/htdocs/hashcode_help.html

  • The Object.equals() Javadoc

    //java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#equals(java.lang.Object)

  • The Object.hashCode() Javadoc

    //java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#hashCode()

  • For Joshua Bloch's Effective Java Programming Language Guide (Addison Wesley Professional, 2001; ISBN0201310058), go to

    //www.amazon.com/exec/obidos/ASIN/0201310058/javaworld

  • For more articles on Java classes and methods, browse the APIs section of JavaWorld's Topical Index

    //www.javaworld.com/channel_content/jw-apis-index.shtml

  • Want more? See the Java Q&A index page for the full Q&A catalog

    //www.javaworld.com/columns/jw-qna-index.shtml

  • Pour plus de 100 conseils Java perspicaces de certains des meilleurs esprits dans l'entreprise, visitez le « JavaWorld de Java Conseils page d' index

    //www.javaworld.com/columns/jw-tips-index.shtml

  • Apprenez les bases de Java dans notre discussion Java pour débutants

    //forums.idg.net/[email protected]@.ee6b804

  • Inscrivez-vous au bulletin électronique hebdomadaire gratuit de JavaWorld sur Core Java

    //www.javaworld.com/subscribe

  • Vous trouverez une multitude d'articles liés à l'informatique provenant de nos publications sœurs sur .net

Cette histoire, "Hashtables" a été initialement publiée par JavaWorld.