Meilleure implémentation de la méthode hashCode pour une collection
https://stackoverflow.com/questions/113511
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Comment décider de la meilleure implémentation de la méthode hashCode () pour une collection (en supposant que la méthode equals a été remplacée correctement)?
La solution
La meilleure implémentation? C'est une question difficile, car elle dépend du modèle d'utilisation.
Dans presque Josh Bloch , Effective Java a été proposé dans presque tous les cas une bonne mise en œuvre raisonnable. La meilleure chose à faire est de regarder là-bas, car l'auteur explique pourquoi l'approche est bonne.
Une version courte
-
Créez un résultat
intet affectez une valeur non nulle . -
Pour tous les champs
ftestés dans la méthodeequals (), calculez un code de hachagecpar:- Si le champ f est un
booléen: calculer(f? 0: 1); - Si le champ f est un
octet,char,courtouint: calculez( int) f; - Si le champ f est un
long: calculez(int) (f ^ (f> g>; 32)); - Si le champ f est un
float: calculezFloat.floatToIntBits (f); - Si le champ f est un
double: calculezDouble.doubleToLongBits (f)et gérez la valeur de retour comme chaque valeur longue; - Si le champ f est un objet : utilisez le résultat de la méthode
hashCode ()ou 0 sif == null; - Si le champ f est un tableau : affichez chaque champ en tant qu'élément distinct et calculez la valeur de hachage de manière récursive et combinez les valeurs comme décrit ci-après.
- Si le champ f est un
-
Combinez la valeur de hachage
cavecrésultat:result = 37 * result + c -
Renvoyer
résultat
Cela devrait entraîner une distribution appropriée des valeurs de hachage pour la plupart des situations d'utilisation.
Autres conseils
Si vous êtes satisfait de l'implémentation Java efficace recommandée par dmeister, vous pouvez utiliser un appel de bibliothèque au lieu de lancer le vôtre:
@Override
public int hashCode() {
return Objects.hashCode(this.firstName, this.lastName);
}
Ceci nécessite soit de la goyave ( com.google.common.base.Objects.hashCode ) ou de la bibliothèque standard en Java 7 ( java.util.Objects.hash ). mais fonctionne de la même manière.
Il est préférable d’utiliser la fonctionnalité fournie par Eclipse, qui fait un très bon travail. Vous pouvez consacrer vos efforts et votre énergie au développement de la logique commerciale.
Bien que cela soit lié à documentation Android (Wayback Machine) et Mon propre code sur Github , cela fonctionnera pour Java en général. Ma réponse est une extension de la Réponse de dmeister avec un code beaucoup plus facile à lire et à comprendre.
@Override
public int hashCode() {
// Start with a non-zero constant. Prime is preferred
int result = 17;
// Include a hash for each field.
// Primatives
result = 31 * result + (booleanField ? 1 : 0); // 1 bit » 32-bit
result = 31 * result + byteField; // 8 bits » 32-bit
result = 31 * result + charField; // 16 bits » 32-bit
result = 31 * result + shortField; // 16 bits » 32-bit
result = 31 * result + intField; // 32 bits » 32-bit
result = 31 * result + (int)(longField ^ (longField >>> 32)); // 64 bits » 32-bit
result = 31 * result + Float.floatToIntBits(floatField); // 32 bits » 32-bit
long doubleFieldBits = Double.doubleToLongBits(doubleField); // 64 bits (double) » 64-bit (long) » 32-bit (int)
result = 31 * result + (int)(doubleFieldBits ^ (doubleFieldBits >>> 32));
// Objects
result = 31 * result + Arrays.hashCode(arrayField); // var bits » 32-bit
result = 31 * result + referenceField.hashCode(); // var bits » 32-bit (non-nullable)
result = 31 * result + // var bits » 32-bit (nullable)
(nullableReferenceField == null
? 0
: nullableReferenceField.hashCode());
return result;
}
MODIFIER
Généralement, lorsque vous remplacez hashcode (...) , vous souhaitez également remplacer est égal à (...) . Donc, pour ceux qui vont ou ont déjà implémenté est égal à , voici une bonne référence de mon github ...
@Override
public boolean equals(Object o) {
// Optimization (not required).
if (this == o) {
return true;
}
// Return false if the other object has the wrong type, interface, or is null.
if (!(o instanceof MyType)) {
return false;
}
MyType lhs = (MyType) o; // lhs means "left hand side"
// Primitive fields
return booleanField == lhs.booleanField
&& byteField == lhs.byteField
&& charField == lhs.charField
&& shortField == lhs.shortField
&& intField == lhs.intField
&& longField == lhs.longField
&& floatField == lhs.floatField
&& doubleField == lhs.doubleField
// Arrays
&& Arrays.equals(arrayField, lhs.arrayField)
// Objects
&& referenceField.equals(lhs.referenceField)
&& (nullableReferenceField == null
? lhs.nullableReferenceField == null
: nullableReferenceField.equals(lhs.nullableReferenceField));
}
Tout d’abord, assurez-vous que Equals est correctement implémenté. un article IBM DeveloperWorks :
- Symétrie: pour deux références, a et b, a.equals (b) si et seulement si b.equals (a)
- Réflexivité: pour toutes les références non NULL, a.equals (a)
- Transitivité: si a.equals (b) et b.equals (c), alors a.equals (c)
Assurez-vous ensuite que leur relation avec hashCode respecte le contact (du même article):
- Cohérence avec hashCode (): deux objets identiques doivent avoir la même valeur hashCode ()
Enfin, une bonne fonction de hachage doit s’efforcer d’approcher de la fonction de hachage idéale .
about8.blogspot.com, vous avez dit
si equals () renvoie true pour deux objets, alors hashCode () devrait renvoyer la même valeur. Si equals () renvoie false, hashCode () doit retourner des valeurs différentes
Je ne peux pas être d'accord avec vous. Si deux objets ont le même hashcode, cela ne signifie pas nécessairement qu'ils sont égaux.
Si A est égal à B, alors A.hashcode doit être égal à B.hascode
mais
si A.hashcode est égal à B.hascode, cela ne signifie pas que A doit être égal à B
Si vous utilisez eclipse, vous pouvez générer equals () et hashCode () en utilisant:
Source - > Générez hashCode () et equals ().
À l'aide de cette fonction, vous pouvez choisir les champs que vous souhaitez utiliser pour le calcul de l'égalité et du code de hachage. Eclipse génère les méthodes correspondantes.
Il existe une bonne implémentation de la logique Effective Java de hashcode () et equals () dans Apache Commons Lang . Commander HashCodeBuilder et EqualsBuilder .
Juste une petite note pour compléter une autre réponse plus détaillée (en terme de code):
Si je considère la question how-do-i- créer une table de hachage en java et en particulier le jGuru FAQ entry , je pense que d’autres critères permettent de juger un code de hachage sont les suivants:
- synchronisation (l’algo supporte-t-il ou non l’accès simultané?)
- échec de l'itération sécurisée (l'algo détecte-t-il une collection qui change pendant l'itération)
- valeur null (le code de hachage prend-il en charge la valeur null dans la collection)
Si je comprends bien votre question, vous avez une classe de collection personnalisée (c'est-à-dire une nouvelle classe qui s'étend à partir de l'interface Collection) et vous souhaitez implémenter la méthode hashCode ().
Si votre classe de collection étend AbstractList, vous n'avez pas à vous en soucier, il existe déjà une implémentation de equals () et hashCode () qui fonctionne en itérant à travers tous les objets et en ajoutant leurs hashCodes ().
public int hashCode() {
int hashCode = 1;
Iterator i = iterator();
while (i.hasNext()) {
Object obj = i.next();
hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
}
return hashCode;
}
Maintenant, si ce que vous voulez est le meilleur moyen de calculer le code de hachage pour une classe spécifique, j'utilise normalement l'opérateur ^ (exclus au niveau du bit ou) au traitement de tous les champs que j'utilise dans la méthode equals:
public int hashCode(){
return intMember ^ (stringField != null ? stringField.hashCode() : 0);
}
@ about8: il y a un bug assez sérieux.
Zam obj1 = new Zam("foo", "bar", "baz");
Zam obj2 = new Zam("fo", "obar", "baz");
même hashcode
vous voulez probablement quelque chose comme
public int hashCode() {
return (getFoo().hashCode() + getBar().hashCode()).toString().hashCode();
(pouvez-vous obtenir hashCode directement à partir d'Int en Java ces jours-ci? Je pense que cela fait de l'autocast .. si c'est le cas, sautez le toString, c'est moche.)
Comme vous avez spécifiquement demandé des collections, j'aimerais ajouter un aspect que les autres réponses n'ont pas encore mentionné: un tableau de hachage ne s'attend pas à ce que leurs clés changent leur code de hachage une fois ajoutées à la collection. Est-ce que cela irait à l'encontre du but recherché?
Utilisez les méthodes de réflexion sur Apache Commons EqualsBuilder et HashCodeBuilder .
toute méthode de hachage qui répartit la valeur de hachage de manière uniforme sur la plage possible est une bonne implémentation. Voir efficace java ( = "nofollow noreferrer"> http://books.google.com.au/books?id=ZZOiqZQIbRMC&dq=effective+java&pg=PP1&ots=UZMZ2siN25&sig=kR0n73DHJOn X & amp; oi = book_result & resnum = 1 & ct = result ), il existe un bon conseil pour la mise en oeuvre du hashcode (élément 9, je pense ...).
Je préfère utiliser les méthodes utilitaires de Google Collections, lib de la classe Objects , qui m'aident à garder mon code propre. Très souvent, est égal à et les méthodes hashcode sont créées à partir du modèle de l'EDI, elles ne sont donc pas propres à la lecture.
J'utilise un petit wrapper autour de Arrays.deepHashCode (...) car il gère correctement les tableaux fournis en tant que paramètres
public static int hash(final Object... objects) {
return Arrays.deepHashCode(objects);
}
Voici une autre démonstration de l’approche JDK 1.7+ avec des logiques de superclasse comptabilisées. Je le vois comme très pratique avec la classe Object hashCode (), une dépendance JDK pure et aucun travail manuel supplémentaire. Veuillez noter que Objects.hash () est null tolérant.
Je n'ai inclus aucune implémentation de equals () mais en réalité, vous en aurez bien besoin.
import java.util.Objects;
public class Demo {
public static class A {
private final String param1;
public A(final String param1) {
this.param1 = param1;
}
@Override
public int hashCode() {
return Objects.hash(
super.hashCode(),
this.param1);
}
}
public static class B extends A {
private final String param2;
private final String param3;
public B(
final String param1,
final String param2,
final String param3) {
super(param1);
this.param2 = param2;
this.param3 = param3;
}
@Override
public final int hashCode() {
return Objects.hash(
super.hashCode(),
this.param2,
this.param3);
}
}
public static void main(String [] args) {
A a = new A("A");
B b = new B("A", "B", "C");
System.out.println("A: " + a.hashCode());
System.out.println("B: " + b.hashCode());
}
}
L'implémentation standard est faible et son utilisation entraîne des collisions inutiles. Imaginez un
class ListPair {
List<Integer> first;
List<Integer> second;
ListPair(List<Integer> first, List<Integer> second) {
this.first = first;
this.second = second;
}
public int hashCode() {
return Objects.hashCode(first, second);
}
...
}
Maintenant,
new ListPair(List.of(a), List.of(b, c))
et
new ListPair(List.of(b), List.of(a, c))
a le même hashCode , à savoir 31 * (a + b) + c en tant que multiplicateur utilisé pour List.hashCode est réutilisé ici . De toute évidence, les collisions sont inévitables, mais produire des collisions inutiles est tout simplement… inutile.
L'utilisation de 31 n'a rien de vraiment intelligent. Le multiplicateur doit être impair pour éviter de perdre des informations (tout multiplicateur pair perd au moins le bit le plus significatif, des multiples de quatre en perdent deux, etc.). Tout multiplicateur impair est utilisable. De petits multiplicateurs peuvent conduire à un calcul plus rapide (le JIT peut utiliser des décalages et des ajouts), mais étant donné que la multiplication n'a qu'une latence de trois cycles sur les processeurs Intel / AMD modernes, cela n'a guère d'importance. De petits multiplicateurs entraînent également plus de collision pour de petites entrées, ce qui peut parfois poser problème.
Utiliser un nombre premier est inutile car les nombres premiers n’ont aucune signification dans l’anneau Z / (2 ** 32).
Donc, je vous conseillerais d'utiliser un grand nombre impair choisi au hasard (n'hésitez pas à prendre une prime). Étant donné que les processeurs i86 / amd64 peuvent utiliser une instruction plus courte pour les opérandes dans un seul octet signé, les multiplicateurs tels que 109 présentent un avantage minime en termes de rapidité. Pour réduire les collisions, prenez quelque chose comme 0x58a54cf5.
Utiliser différents multiplicateurs à différents endroits est utile, mais probablement pas suffisant pour justifier le travail supplémentaire.
Lors de la combinaison de valeurs de hachage, j'utilise généralement la méthode de combinaison utilisée dans la bibliothèque boost c ++, à savoir:
seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
Cela permet assez bien d’assurer une distribution uniforme. Pour en savoir plus sur le fonctionnement de cette formule, voir l'article de StackOverflow: Nombre magique dans boost :: hash_combine
Il existe une bonne discussion sur les différentes fonctions de hachage à l'adresse: http://burtleburtle.net/bob /hash/doobs.html
Pour une classe simple, il est souvent plus simple d'implémenter hashCode () en fonction des champs de classe vérifiés par l'implémentation equals ().
public class Zam {
private String foo;
private String bar;
private String somethingElse;
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
Zam otherObj = (Zam)obj;
if ((getFoo() == null && otherObj.getFoo() == null) || (getFoo() != null && getFoo().equals(otherObj.getFoo()))) {
if ((getBar() == null && otherObj. getBar() == null) || (getBar() != null && getBar().equals(otherObj. getBar()))) {
return true;
}
}
return false;
}
public int hashCode() {
return (getFoo() + getBar()).hashCode();
}
public String getFoo() {
return foo;
}
public String getBar() {
return bar;
}
}
Le plus important est de garder hashCode () et equals () cohérents: si equals () renvoie true pour deux objets, alors hashCode () devrait renvoyer la même valeur. Si equals () renvoie false, hashCode () doit renvoyer des valeurs différentes.
