C # Comment sélectionner un Hashcode pour une classe qui enfreint le contrat Equals?

Question

J'ai plusieurs classes qui, pour certaines raisons, ne suivent pas le contrat officiel Est égal à . Dans le GetHashCode () écrasé, ces classes renvoient simplement 0 afin qu'elles puissent être utilisées dans un tableau de hachage.

Certaines de ces classes implémentent la même interface et des cartes de hachage utilisent cette interface comme clé. J'ai donc pensé que chaque classe devrait au moins renvoyer une valeur différente (mais toujours constante) dans GetHashCode () .

La question est de savoir comment sélectionner cette valeur. Dois-je simplement laisser la première classe revenir 1, la prochaine classe 2 et ainsi de suite? Ou devrais-je essayer quelque chose comme

class SomeClass : SomeInterface {
    public overwrite int GetHashCode() {
        return "SomeClass".GetHashCode();
    }
}

alors le hash est distribué plus uniformément? (Dois-je mettre en cache la valeur renvoyée moi-même ou le compilateur de Microsoft peut-il l'optimiser?)

Mise à jour: Il n'est pas possible de renvoyer un code de hachage individuel pour chaque objet, car Égale enfreint le contrat. Spécifiquement, je me réfère à ce problème .

Answer 1

J'ai rencontré ce problème lors de l'écriture d'une classe de vecteurs. Je voulais comparer les vecteurs pour l’égalité, mais les opérations de type float entraînant des erreurs d’arrondi, je voulais donc une égalité approximative. En résumé, il est préférable de ne pas prendre d’égales, sauf si votre implémentation est symétrique, réflexive et transitive.

D'autres classes vont supposer qu'égal à égaux a ces propriétés, de même que les classes qui utilisent ces classes, vous pouvez donc vous retrouver dans des cas étranges. Par exemple, une liste peut imposer l’unicité, mais se termine avec deux éléments dont l’évaluation est égale à un élément B.

Une table de hachage est l'exemple parfait d'un comportement imprévisible lorsque vous rompez l'égalité. Par exemple:

//Assume a == b, b == c, but a != c
var T = new Dictionary<YourType, int>()
T[a] = 0
T[c] = 1
return T[b] //0 or 1? who knows!

Un autre exemple serait un ensemble:

//Assume a == b, b == c, but a != c
var T = new HashSet<YourType>()
T.Add(a)
T.Add(c)
if (T.contains(b)) then T.remove(b)
//surely T can't contain b anymore! I sure hope no one breaks the properties of equality!
if (T.contains(b)) then throw new Exception()

Je suggère d'utiliser une autre méthode, avec un nom comme ApproxEquals. Vous pouvez également envisager de remplacer l'opérateur ==, car il n'est pas virtuel et ne sera donc pas utilisé accidentellement par d'autres classes comme Equals pourrait l'être.

Si vous ne pouvez vraiment pas utiliser l'égalité de référence pour la table de hachage, ne gâchez pas les performances des cas dans lesquels vous le pouvez. Ajoutez une interface IApproxEquals, implémentez-la dans votre classe et ajoutez une méthode d'extension GetApprox à Dictionary qui énumère les clés qui en recherchent une approximativement égale et renvoie la valeur associée. Vous pouvez également écrire un dictionnaire personnalisé, en particulier pour les vecteurs tridimensionnels, ou ce dont vous avez besoin.

Answer 2

S'il "viole le contrat d'égalité", je ne suis pas sûr que vous deviez l'utiliser comme clé.

Si quelque chose utilise ça comme clé, vous avez vraiment besoin de faire le hachage correctement ... la logique égale à est très floue, mais deux valeurs considérées comme égales à doit avoir le même code de hachage. Il n'est pas nécessaire que deux valeurs avec le même code de hachage soient égales.

L'utilisation d'une chaîne constante n'aidera pas grand-chose - vous obtiendrez une répartition égale des valeurs sur les types, mais c'est à peu près tout ...

Answer 3

Je suis curieux de savoir quel serait le raisonnement pour remplacer GetHashCode () et renvoyer une valeur constante. Pourquoi violer l’idée d’un hash plutôt que de violer le "contrat"? et ne pas ignorer la fonction GetHashCode () et laisser l'implémentation par défaut de Object ?

Modifier

Si ce que vous avez fait est de faire en sorte que vos objets correspondent en fonction de leur contenu plutôt que de leur référence, ce que vous proposez de faire en sorte que différentes classes utilisent simplement des constantes différentes peut fonctionner, mais est très inefficace. Vous voulez créer un algorithme de hachage capable de récupérer le contenu de votre classe et de produire une valeur qui équilibre la vitesse avec une distribution égale (c'est le hachage 101).

Je suppose que je ne suis pas sûr de ce que vous recherchez ... il n'y a pas de "bon" schéma pour choisir des nombres constants pour ce paradigme. L'un n'est pas meilleur que l'autre. Essayez d’améliorer vos objets pour créer un véritable hachage.

Answer 4

Lorsque des collisions de hachage se produisent, HashTable / Dictionary appelle Equals pour rechercher la clé que vous recherchez. L'utilisation d'un code de hachage constant supprime les avantages de la vitesse d'utilisation d'un hachage en premier lieu - elle devient une recherche linéaire.

Vous dites que la méthode Equals n’a pas été mise en œuvre conformément au contrat. Que voulez-vous dire exactement avec cela? Selon le type de violation, la HashTable ou le Dictionnaire sera simplement lent (recherche linéaire) ou ne fonctionnera pas du tout.