Je crois que la plupart des gens connaissent la structure des données de la table de hachage, et dans de nombreux endroits, les tables de hachage sont utilisées pour améliorer l'efficacité de la recherche. Il existe une méthode dans la classe d'objets de Java:
public native int hashcode ();
Selon la déclaration de cette méthode, on peut voir que la méthode renvoie une valeur numérique de type int et est une méthode locale, donc aucune implémentation spécifique n'est donnée dans la classe d'objets.
Pourquoi la classe d'objets a-t-elle besoin d'une telle méthode? Quelle est sa fonction? Aujourd'hui, nous discuterons en détail de la méthode HashCode.
1. La fonction de la méthode de code de hash
Pour les langages de programmation contenant des types de conteneurs, HashCode est essentiellement impliqué. Il en va de même pour Java. La fonction principale de la méthode HashCode est de fonctionner normalement avec des ensembles basés sur le hachage, ces ensembles de hachage incluent HashSet, HashMap et Hashtable.
Pourquoi le dites-vous? Considérez une situation où lorsqu'un objet est inséré dans une collection, comment déterminer si l'objet existe déjà dans la collection? (Remarque: les éléments en double ne sont pas autorisés dans la collection)
Peut-être que la plupart des gens penseront à appeler la méthode égale pour comparer une par une, et cette méthode est en effet possible. Cependant, s'il y a déjà dix mille éléments de données ou plus dans l'ensemble, si la méthode égale est utilisée pour comparer une par une, l'efficacité sera inévitablement un problème. À l'heure actuelle, la fonction de la méthode HashCode est reflétée. Lorsqu'un nouvel objet doit être ajouté à la collection, la méthode HashCode de l'objet est appelée d'abord pour obtenir la valeur HashCode correspondante. En fait, dans la mise en œuvre spécifique de HashMap, un tableau sera utilisé pour enregistrer la valeur de code de hash de l'objet qui a été enregistré. S'il n'y a pas de valeur de code de hash dans le tableau, il peut être stocké directement sans aucune comparaison. Si la valeur HashCode existe, sa méthode égale est appelée à comparer avec le nouvel élément. Si la même chose est vraie, d'autres adresses ne seront pas stockées. Par conséquent, il y a un problème de résolution des conflits ici. De cette façon, le nombre de fois où la méthode égale est réellement appelée est considérablement réduite. Pour le dire simplement: la méthode HashCode en Java mappe les informations liées à l'objet (telles que l'adresse de stockage de l'objet, le champ de l'objet, etc.) dans une valeur numérique en fonction de certaines règles, et cette valeur est appelée valeur de hachage. Le code suivant est la mise en œuvre spécifique de la méthode de put dans java.util.hashmap:
public v put (k key, v valeur) {if (key == null) return putFornullKey (value); int hash = hash (key.hashcode ()); int i = indexfor (hash, table.length); pour (entrée <k, v> e = table [i]; e! = null; e = e.next) {objet k; if (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v oldValue = e.Value; e.Value = valeur; e.recordAccess (this); Retour OldValue; }} modCount ++; Addentry (hachage, clé, valeur, i); retourner null; } La méthode de put est utilisée pour ajouter un nouvel élément au hashmap. À partir de l'implémentation spécifique de la méthode de put, nous pouvons savoir que la méthode HashCode sera d'abord appelée pour obtenir la valeur de code de hashcode de l'élément, puis vérifier si la valeur de code de hash existe dans le tableau. S'il existe, appelez la méthode égale pour redéterminer si l'élément existe. S'il existe, mettez à jour la valeur de la valeur, sinon ajoutez le nouvel élément au hashmap. À partir de là, nous pouvons voir que la méthode HashCode existe pour réduire le nombre d'appels à la méthode égaux et ainsi améliorer l'efficacité du programme.
Certains amis pensent à tort que par défaut, HashCode renvoie l'adresse de stockage de l'objet. En fait, cette vue est incomplète. Il est vrai que certains JVM renvoient directement l'adresse de stockage de l'objet lors de la mise en œuvre, mais ce n'est pas le cas la plupart du temps. On peut dire que l'adresse de stockage peut y être liée. Ce qui suit est la mise en œuvre de la génération de valeurs de hachage de hachage dans Hotspot JVM:
static inline intptr_t get_next_hash (thread * self, oop obj) {intptr_t value = 0; if (hashcode == 0) {// Ce formulaire utilise un RNG global de parc de parc mondial non gardé, // il est donc possible pour deux fils de courir et de générer le même RNG. // Sur le système MP, nous aurons beaucoup d'accès RW à un monde, donc le mécanisme // induit beaucoup de trafic de cohérence. valeur = os :: random (); } else if (hashcode == 1) {// Cette variation a la propriété d'être stable (idempotent) // entre les opérations STW. Cela peut être utile dans certains des schémas de synchronisation 1-0 //. intptr_t addRbits = intptr_t (obj) >> 3; valeur = addrbits ^ (addrbits >> 5) ^ gvars.stwrandom; } else if (hashcode == 2) {value = 1; // pour les tests de sensibilité} else if (hashcode == 3) {value = ++ gvars.hcSequence; } else if (hashcode == 4) {value = intptr_t (obj); } else {// Schéma XOR-Shift de Marsaglia avec un état spécifique au thread // C'est probablement la meilleure implémentation globale - nous // nous en ferons probablement la valeur par défaut dans les versions futures. non signé t = self -> _ hashStatex; t ^ = (t << 11); Self -> _ hashStatex = self -> _ hashStatey; Self -> _ hashStatey = self -> _ hashStatez; Self -> _ hashStatez = self -> _ hashStatew; Unsigned v = self -> _ hashStatew; v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)); Self -> _ hashStatew = v; valeur = v; } valeur & = markoopdes :: hash_mask; if (valeur == 0) value = 0xbad; affirmer (valeur! = MarkoopDesc :: no_hash, "invariant"); Tevent (HashCode: Generate); valeur de retour;}Cette implémentation est située dans le fichier HotSpot / Src / Share / VM / Runtime / Synchronizer.cpp.
Par conséquent, certaines personnes peuvent dire que pouvons-nous juger directement si deux objets sont égaux en fonction de la valeur de code de hash? Ce n'est certainement pas possible, car différents objets peuvent générer la même valeur de code de hash. Bien qu'il ne soit pas possible de juger si deux objets sont égaux sur la base de la valeur de code de hash, vous pouvez directement juger que les deux objets ne sont pas égaux en fonction de la valeur de code hash. Si les valeurs de code de hash des deux objets ne sont pas égales, elles doivent être deux objets différents. Si vous souhaitez déterminer si deux objets sont vraiment égaux, vous devez utiliser la méthode Equals.
C'est-à-dire que pour deux objets, si le résultat obtenu en appelant la méthode Equal est vrai, les valeurs de code de hash-code des deux objets doivent être égales;
Si le résultat obtenu par la méthode Equals est faux, les valeurs de code de hash des deux objets peuvent ne pas être différentes;
Si les valeurs de code de hash des deux objets ne sont pas égales, le résultat obtenu par la méthode égaux doit être faux;
Si les valeurs de code de hash des deux objets sont égales, le résultat obtenu par la méthode égaux est inconnu.
2. Méthode égale et méthode de code hash
Dans certains cas, lors de la conception d'une classe, les programmeurs doivent réécrire la méthode Equals, telle que la classe String, mais assurez-vous de noter que lors de la réécriture de la méthode Equals, ils doivent réécrire la méthode Hashcode. Pourquoi le dites-vous?
Voyons un exemple ci-dessous:
package com.cxh.test1; importer java.util.hashmap; import java.util.hashset; import java.util.set; class les gens {nom de chaîne privé; Âge privé; Les gens publics (nom de chaîne, int age) {this.name = name; this.age = âge; } public void Setage (int Age) {this.age = age; } @Override public boolean equals (objet obj) {// TODO Méthode générée automatiquement Stub return this.name.equals (((peuple) obj) .name) && this.age == ((peuple) obj) .age; }} classe publique Main {public static void main (String [] args) {People P1 = new People ("Jack", 12); System.out.println (p1.hashcode ()); Hashmap <People, Integer> hashmap = new hashmap <People, Integer> (); hashmap.put (P1, 1); System.out.println (hashmap.get (New People ("Jack", 12));}}Ici, je n'ai réécrit que la méthode égaux, ce qui signifie que si deux objets de personnes ont le même nom et l'âge, ils sont considérés comme la même personne.
L'intention d'origine de ce code est de sortir le résultat de "1", mais en fait, il étend "NULL". Pourquoi? La raison en est que vous oubliez de réécrire la méthode HashCode lors de la réécriture de la méthode Equals.
Bien que deux objets avec le même nom et l'âge soient logiquement déterminés comme égaux (similaires à la classe de chaîne), il convient de savoir que par défaut, la méthode HashCode mappe l'adresse de stockage de l'objet. Ensuite, il n'est pas surprenant que le résultat de sortie du code ci-dessus soit "nul". La raison est très simple, l'objet pointé par P1 et
System.out.println (hashmap.get (New People ("Jack", 12)); The New People ("Jack", 12) dans cette phrase génère deux objets, et leurs adresses de stockage doivent être différentes. Ce qui suit est la mise en œuvre spécifique de la méthode GET de HashMap:
public v get (object key) {if (key == null) return getFornullKey (); int hash = hash (key.hashcode ()); pour (entrée <k, v> e = table [indexfor (hash, table.length)]; e! = null; e = e.next) {objet k; if (e.hash == hash && ((k = e.key) == key || key.equals (k))) return e.Value; } return null; }Par conséquent, lorsque le hashmap est utilisé pour l'obtenir, car les valeurs de hashcdoe obtenues sont différentes (notez que le code ci-dessus peut obtenir la même valeur de code de hash dans certains cas, mais la probabilité est relativement petite, car bien que les adresses de stockage des deux objets ne soient pas différentes, il est possible d'obtenir la même valeur de Hashcode), donc la boucle pour la boucle ne sera pas exécutée dans la méthode GET et sera directement retournée nulle.
Par conséquent, si vous souhaitez que le code ci-dessus puisse sortir le résultat "1", c'est très simple. Il vous suffit de réécrire la méthode HashCode et de rendre la méthode Equals et HashCode toujours logiquement cohérente.
package com.cxh.test1; import java.util.hashmap; import java.util.hashset; import java.util.set; classe People {nom de chaîne privée; Âge privé; Les gens publics (nom de chaîne, int age) {this.name = name; this.age = âge; } public void Setage (int Age) {this.age = age; } @Override public int hashcode () {// TODO Méthode générée automatique Stume de retour nom.hashcode () * 37 + âge; } @Override public boolean equals (objet obj) {// TODO Méthode générée automatiquement Stub return this.name.equals (((peuple) obj) .name) && this.age == ((peuple) obj) .age; }} classe publique Main {public static void main (String [] args) {People P1 = new People ("Jack", 12); System.out.println (p1.hashcode ()); Hashmap <People, Integer> hashmap = new hashmap <People, Integer> (); hashmap.put (P1, 1); System.out.println (hashmap.get (New People ("Jack", 12))); }}De cette façon, le résultat de sortie sera "1".
Le passage suivant est extrait du livre Efficace Java:
Pendant l'exécution du programme, tant que les informations utilisées dans le fonctionnement de comparaison de la méthode Equal n'ont pas été modifiées, la méthode HashCode doit toujours renvoyer le même entier.
Si les deux objets sont égaux en fonction de la méthode Equal, alors l'appel de la méthode HashCode des deux objets doit renvoyer le même résultat entier.
Si les deux objets sont comparés l'inégalité selon la méthode Equals, la méthode HashCode ne renvoie pas nécessairement des entiers différents.
Il est facile de comprendre les deuxième et troisième articles, mais le premier article est souvent ignoré. Il y a aussi un passage similaire au premier de la page P495 dans le livre "Java Programming Thought":
"Le facteur le plus important lors de la conception de HashCode () est: chaque fois que vous appelez HashCode () sur le même objet, la même valeur doit être générée. Si un objet est ajouté au hashmap avec put (), et une autre valeur de code de hash est générée lorsqu'elle est retirée avec get (), alors l'objet ne peut pas être obtenu. La méthode hashcode () générera un code de hachage différent. "
Voici un exemple:
package com.cxh.test1; Importer java.util.hashmap; import java.util.hashset; import java.util.set; class les gens {nom de chaîne privé; Âge privé; Les gens publics (nom de chaîne, int age) {this.name = name; this.age = âge; } public void Setage (int Age) {this.age = age; } @Override public int hashcode () {// TODO Méthode générée automatique Stume de retour nom.hashcode () * 37 + âge; } @Override public boolean equals (objet obj) {// TODO Méthode générée automatiquement Stub return this.name.equals (((peuple) obj) .name) && this.age == ((peuple) obj) .age; }} classe publique Main {public static void main (String [] args) {People P1 = new People ("Jack", 12); System.out.println (p1.hashcode ()); Hashmap <People, Integer> hashmap = new hashmap <People, Integer> (); hashmap.put (P1, 1); p1.setage (13); System.out.println (hashmap.get (p1)); }}Le résultat de cette sortie de code est "nul", et tout le monde doit être clair sur les raisons.
Par conséquent, lors de la conception des méthodes de code de hash et égal aux méthodes, si les données de l'objet sont volatiles, il est préférable de ne pas s'appuyer sur ce champ dans les méthodes égales et les méthodes de code de hash.
Ce qui précède est tout le contenu de cet article. J'espère que cela sera utile à l'apprentissage de tous et j'espère que tout le monde soutiendra davantage Wulin.com.