Comment s'assurer que hashCode () est compatible avec equals ()?
https://stackoverflow.com/questions/410236
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Lors de la substitution de la fonction equals () de java.lang.Object, les javadocs suggèrent que,
il est généralement nécessaire de remplacer la méthode hashCode chaque fois que cette méthode est remplacée, de manière à conserver le contrat général de la méthode hashCode, qui indique que les objets identiques doivent avoir les mêmes codes de hachage.
La méthode hashCode () doit renvoyer un entier unique pour chaque objet (cela est facile à faire lorsque vous comparez des objets en fonction de l'emplacement de la mémoire, il vous suffit de renvoyer l'adresse unique . de l'objet)
Comment une méthode hashCode () doit-elle être remplacée de manière à renvoyer un entier unique pour chaque objet basé uniquement sur les propriétés de cet objet?
public class People{
public String name;
public int age;
public int hashCode(){
// How to get a unique integer based on name and age?
}
}
/*******************************/
public class App{
public static void main( String args[] ){
People mike = new People();
People melissa = new People();
mike.name = "mike";
mike.age = 23;
melissa.name = "melissa";
melissa.age = 24;
System.out.println( mike.hasCode() ); // output?
System.out.println( melissa.hashCode(); // output?
}
}
La solution
Cela ne dit pas que le hashcode d'un objet doit être complètement unique, mais que le hashcode de deux objets égaux renvoie le même hashcode. Il est tout à fait légal que deux objets non égaux renvoient le même hashcode. Toutefois, plus une distribution de hashcode est unique sur un ensemble d'objets, meilleures seront les performances obtenues avec HashMaps et les autres opérations utilisant le hashCode.
Les IDE tels que IntelliJ Idea ont des générateurs intégrés pour les égaux et hashCode qui font généralement un très bon travail pour trouver & "Assez bon &"; code pour la plupart des objets (et probablement meilleur que certaines fonctions de hachage trop astucieuses).
Par exemple, voici une fonction hashCode générée par Idea pour votre classe People:
public int hashCode() {
int result = name != null ? name.hashCode() : 0;
result = 31 * result + age;
return result;
}
Autres conseils
Je n’entrerai pas dans les détails de l’unicité de hashCode, car Marc l’a déjà abordée. Pour votre People classe, vous devez d’abord décider de ce que l’égalité d’une personne signifie. Peut-être que l'égalité est basée uniquement sur leur nom, peut-être que sur leur nom et leur âge. Ce sera spécifique à un domaine. Disons que l'égalité est basée sur le nom et l'âge. Votre equals redéfini ressemblerait à
public boolean equals(Object obj) {
if (this==obj) return true;
if (obj==null) return false;
if (!(getClass().equals(obj.getClass())) return false;
Person other = (Person)obj;
return (name==null ? other.name==null : name.equals(other.name)) &&
age==other.age;
}
Chaque fois que vous remplacez hashCode, vous devez remplacer <=>. De plus, <=> ne peut utiliser plus de champs que <=> dans ses calculs. La plupart du temps, vous devez ajouter ou exclusif - ou le code de hachage des différents champs (hashCode devrait être rapide à calculer). Donc, une <=> méthode valide pourrait ressembler à:
public int hashCode() {
return (name==null ? 17 : name.hashCode()) ^ age;
}
Notez que ce qui suit est non valide car il utilise un champ que <=> n'a pas (hauteur). Dans ce cas, deux & Quot; sont égaux à & Quot; les objets peuvent avoir un code de hachage différent.
public int hashCode() {
return (name==null ? 17 : name.hashCode()) ^ age ^ height;
}
En outre, il est parfaitement valide que deux objets non égaux aient le même code de hachage:
public int hashCode() {
return age;
}
Dans ce cas, Jane n'a pas 30 ans, mais Bob et ses deux codes de hachage sont tous deux égaux à 30. Bien que cela soit valide, cela n'est pas souhaitable pour les performances dans les collections basées sur le hachage.
Une autre question demande s’il existe des informations de base de bas niveau que tous les programmeurs devraient connaître, et je pense que la recherche de hachage en fait partie. Alors voilà.
Une table de hachage (notez que je n'utilise pas un nom de classe réel) est fondamentalement un tableau de listes chaînées. Pour trouver quelque chose dans la table, vous devez d'abord calculer le hashcode de ce quelque chose, puis le modifiez en fonction de la taille de la table. Il s'agit d'un index dans le tableau et vous obtenez une liste liée à cet index. Vous parcourez ensuite la liste jusqu'à ce que vous trouviez votre objet.
Etant donné que la récupération du tableau est O (1) et que le parcours de la liste chaînée est O (n), vous souhaitez une fonction de hachage qui crée une distribution aussi aléatoire que possible, de sorte que les objets soient hachés sur différentes listes. Chaque objet peut renvoyer la valeur 0 comme code de hachage et une table de hachage fonctionnerait toujours, mais il s'agirait essentiellement d'une longue liste chaînée au niveau de l'élément 0 du tableau.
De manière générale, vous souhaitez également que le tableau soit grand, ce qui augmente les chances que l'objet se trouve dans une liste de longueur 1. Par exemple, Java HashMap augmente la taille du tableau lorsque le nombre d'entrées dans la carte est > 75% de la taille du tableau. Il y a un compromis ici: vous pouvez avoir un grand tableau avec très peu d'entrées et beaucoup de mémoire, ou un tableau plus petit où chaque élément du tableau est une liste avec & Gt; 1 entrées, et perdre du temps à traverser. Un hachage parfait attribuerait à chaque objet un emplacement unique dans le tableau, sans perte d’espace.
Le terme & "; Hash parfait &"; est un terme réel, et dans certains cas, vous pouvez créer une fonction de hachage fournissant un numéro unique pour chaque objet. Cela n'est possible que si vous connaissez l'ensemble de toutes les valeurs possibles. Dans le cas général, vous ne pouvez pas y parvenir et certaines valeurs renverront le même hashcode. C’est une mathématique simple: si vous avez une chaîne de plus de 4 octets, vous ne pouvez pas créer un hashcode unique de 4 octets.
Un élément intéressant: les tableaux de hachage sont généralement dimensionnés en fonction des nombres premiers, afin de donner les meilleures chances d’allocation aléatoire lorsque vous modifiez les résultats, quel que soit le degré aléatoire des codes de hachage.
Modifier en fonction des commentaires:
1) Une liste chaînée n'est pas le seul moyen de représenter les objets qui ont le même hashcode, bien que ce soit la méthode utilisée par JDK 1.5 HashMap. Bien que moins efficace en mémoire qu'un simple tableau, il crée sans doute moins de désagrégation lors de la redistribution (car les entrées peuvent être dissociées d'un compartiment et être reliées à un autre).
2) À partir de JDK 1.4, la classe HashMap utilise un tableau de la taille 2. auparavant, il utilisait 2 ^ N + 1, ce qui, à mon avis, est primordial pour N < = 32. Cela n'accélère pas l'indexation de tableau en soi, mais permet de calculer l'indice de tableau avec un AND au niveau du bit comme une division, comme l'a noté Neil Coffey. Personnellement, je mettrais cela en doute comme une optimisation prématurée, mais étant donné la liste des auteurs sur HashMap, je suppose qu’il ya un réel avantage.
En général, le code de hachage ne peut pas être unique car il existe plus de valeurs que de codes de hachage possibles (entiers). Un bon code de hachage distribue bien les valeurs sur les entiers. Un mauvais lecteur pourrait toujours donner la même valeur et rester logique, il ne ferait que conduire à des tables de hachage inacceptablement inefficaces.
Les valeurs égales doivent avoir la même valeur de hachage pour que les tables de hachage fonctionnent correctement. Sinon, vous pouvez ajouter une clé à une table de hachage, puis essayer de la rechercher via une valeur égale avec un code de hachage différent sans la trouver. Vous pouvez également mettre une valeur égale avec un code de hachage différent et avoir deux valeurs égales à différents endroits de la table de hachage.
En pratique, vous sélectionnez généralement un sous-ensemble de champs à prendre en compte dans les méthodes hashCode () et equals ().
Je pense que vous l'avez mal compris. Le code de hachage ne doit pas nécessairement être unique pour chaque objet (après tout, il s'agit d'un code de hachage) bien que vous ne souhaitiez évidemment pas qu'il soit identique pour tous les objets. Cependant, vous avez besoin que ce soit identique à tous les objets qui sont égaux, sinon des choses comme les collections standard ne fonctionneraient pas (par exemple, vous rechercheriez quelque chose dans le hachage mais ne le trouverez pas).
Pour les attributs simples, certains IDE ont des générateurs de fonctions de hashcode.
Si vous n'utilisez pas d'EDI, envisagez d'utiliser Apahce Commons et la classe HashCodeBuilder
La seule obligation contractuelle de hashCode est d'être cohérent . Les champs utilisés lors de la création de la valeur hashCode doivent être identiques ou constituer un sous-ensemble des champs utilisés dans la méthode equals. Cela signifie que renvoyer 0 pour toutes les valeurs est valide, bien que non efficace.
On peut vérifier si hashCode est cohérent via un test unitaire. J'ai écrit une classe abstraite appelée EqualityTestCase , qui effectue quelques contrôles hashCode. Il suffit simplement d'étendre le scénario de test et de mettre en œuvre deux ou trois méthodes d'usine. Le test est très grossier: si le hashCode est efficace.
C’est ce que nous dit la documentation en ce qui concerne la méthode du code de hachage
@ javadoc
Chaque fois qu'il est appelé le même objet plus d'une fois pendant une exécution d'une application Java, la méthode hashCode doit toujours renvoyer le même entier, à condition qu'aucun informations utilisées dans les comparaisons d'égaux sur l'objet est modifié. Ce entier n'a pas besoin de rester cohérent à partir d'une exécution d'une application à une autre exécution du même application.
Il existe une notion de clé d'entreprise qui détermine le caractère unique d'instances distinctes du même type. Chaque type spécifique (classe) qui modélise une entité distincte du domaine cible (par exemple, un véhicule dans un système de flotte) doit avoir une clé commerciale, qui est représentée par un ou plusieurs champs de classe. Méthodes equals () et hasCode () doivent tous deux être implémentés à l'aide des champs, qui constituent une clé métier. Cela garantit la cohérence des deux méthodes.
