GetHashCode () problème en utilisant xor

StackOverflow https://stackoverflow.com/questions/1008633

  •  06-07-2019
  •  | 
  •  

Question

D'après ce que j'ai compris, vous êtes généralement censé utiliser xor avec GetHashCode () pour générer un int permettant d'identifier vos données par leur valeur (et non par leur référence). Voici un exemple simple: 

class Foo
{
    int m_a;
    int m_b;

    public int A
    {
        get { return m_a; }
        set { m_a = value; }
    }

    public int B
    {
        get { return m_b; }
        set { m_b = value; }
    }

    public Foo(int a, int b)
    {
        m_a = a;
        m_b = b;
    }

    public override int GetHashCode()
    {
        return A ^ B;
    }

    public override bool Equals(object obj)
    {
        return this.GetHashCode() == obj.GetHashCode();
    }
}

L'idée étant, je veux comparer une instance de Foo à une autre en fonction de la valeur des propriétés A et B. Si Foo1.A == Foo2.A et Foo1.B == Foo2.B, nous avons l'égalité. .

Voici le problème: 

Foo one = new Foo(1, 2);
Foo two = new Foo(2, 1);

if (one.Equals(two)) { ... }  // This is true!

Ils produisent tous les deux la valeur 3 pour GetHashCode (), ce qui entraîne le renvoi de la valeur True à Equals (). Évidemment, il s'agit d'un exemple trivial et, avec seulement deux propriétés, je pourrais simplement comparer les propriétés individuelles dans la méthode Equals (). Cependant, avec une classe plus complexe, cela dégénérerait rapidement.

Je sais qu'il est parfois judicieux de définir le code de hachage une seule fois et de toujours renvoyer la même valeur. Cependant, pour les objets modifiables pour lesquels une évaluation de l'égalité est nécessaire, je ne pense pas que cela soit raisonnable.

Quel est le meilleur moyen de gérer les valeurs de propriété pouvant être facilement échangées lors de l'implémentation de GetHashCode ()?

  

Voir aussi

     

Quel est le meilleur algorithme pour un substitué System.Object.GetHashCode?

Était-ce utile?

La solution

Tout d'abord - N'implémentez pas Equals () uniquement en termes de GetHashCode () - des codes de hachage entrent parfois en collision même lorsque les objets ne sont pas égaux.

Le contrat pour GetHashCode () comprend les éléments suivants:

  • différents hashcodes signifie que les objets ne sont vraiment pas égaux
  • idem hashcodes signifie que les objets peuvent être égaux (mais pas forcément)

Andrew Hare a suggéré que j'intègre sa réponse:

Je vous recommanderais de lire ceci solution (de notre propre Jon Skeet , au fait) pour un "meilleur". moyen de calculer un hashcode.

  

Non, ce qui précède est relativement lent et   n'aide pas beaucoup. Certaines personnes utilisent   XOR (par exemple a ^ b ^ c) mais je préfère le   genre de méthode montré dans Josh Bloch   "Effective Java": 

public override int GetHashCode()
{
    int hash = 23;
    hash = hash*37 + craneCounterweightID;
    hash = hash*37 + trailerID;
    hash = hash*37 + craneConfigurationTypeCode.GetHashCode();
    return hash;
}
     

Les 23 et 37 sont des nombres arbitraires   qui sont co-prime.

     

L'avantage de ce qui précède sur le XOR   méthode est que si vous avez un type   qui a deux valeurs qui sont   souvent les mêmes, XORing ceux   les valeurs donneront toujours le même   résultat (0) alors que ce qui précède   différencier entre eux sauf si   vous êtes très malchanceux.

Comme mentionné dans l'extrait ci-dessus, vous pouvez également consulter le livre de Joshua Bloch , Effective Java, qui contient un traitement intéressant du sujet (la discussion sur le hashcode s’applique également à .NET).

Autres conseils

Andrew a publié un bon exemple pour générer un meilleur code de hachage, tout en gardant à l’esprit que vous ne devriez pas utiliser les codes de hachage comme vérification de l’égalité, car ils ne sont pas toujours uniques.

Pour un exemple trivial de la raison pour laquelle il s’agit de considérer un objet double. Il a plus de valeurs possibles qu'un int, il est donc impossible d'avoir un int unique pour chaque double. Les hachages ne sont en réalité qu'un premier passage, utilisé dans des situations comme un dictionnaire lorsque vous avez besoin de trouver la clé rapidement, en comparant d'abord les hachages, un pourcentage important des clés possibles peut être exclu et seules les clés avec des hachages correspondantes doivent supporter le coût. d'une vérification d'égalité complète (ou une autre méthode résolution de collision ).

Le hachage implique toujours des collisions et vous devez le gérer (par exemple, comparez les valeurs de hachage et, si elles sont égales, comparez les valeurs à l'intérieur des classes pour vous assurer qu'elles sont égales).

En utilisant un simple XOR, vous aurez beaucoup de collisions. Si vous voulez moins, utilisez des fonctions mathématiques qui répartissent les valeurs sur différents bits (décalage des bits, multiplication par des nombres premiers, etc.).

Lisez Remplacement de GetHashCode pour des objets mutables? C # et réfléchissez à la mise en œuvre de IEquatable < T >

Une génération rapide et une bonne distribution de hash 

public override int GetHashCode()
{
    return A.GetHashCode() ^ B.GetHashCode();         // XOR
}

Par curiosité, car les codes de hachage sont une mauvaise idée, ne serait-il pas préférable de ne faire que le code suivant, ou est-ce que je manque quelque chose? 

public override bool Equals(object obj)
{
    bool isEqual = false;
    Foo otherFoo = obj as Foo;
    if (otherFoo != null)
    {
        isEqual = (this.A == otherFoo.A) && (this.B == otherFoo.B);
    }
    return isEqual;
}

Il existe plusieurs meilleures implémentations de hachage. hachage FNV , par exemple.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top