C # Wie ein Hashcode für eine Klasse zu wählen, die den Vertrag von equals verletzt?

Question

Ich habe mehrere Klassen bekommt, die aus bestimmten Gründen, nicht dem offiziellen Equals Vertrag nicht folgen. Im überschrieben GetHashCode() kehren diese Klassen einfach 0, so dass sie in einer HashMap verwendet werden.

Einige dieser Klassen die gleiche Schnittstelle implementieren und es gibt HashMaps diese Schnittstelle als Schlüssel. Also dachte ich, dass jede Klasse sollte mindestens einen anderen Rückkehr (aber immer noch konstant) Wertes in GetHashCode().

Die Frage ist, wie dieser Wert zu wählen. Soll ich einfach die erste Klasse Rückkehr 1, die nächste Klasse 2 und so weiter? Oder sollte ich versuchen, so etwas wie

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

so wird der Hash gleichmäßiger verteilt? (Muss ich den zurückgegebenen Wert selbst cachen oder ist Microsofts Compiler in der Lage, dies zu optimieren?)

Update: Es ist nicht möglich, eine individuelle hashcode für jedes Objekt zurück, weil der Vertrag Equals verletzt. Specifially, ich beziehe auf dieses Problem .

Answer 1

Ich lief in genau dieses Problem, wenn eine Vektor-Klasse zu schreiben. Ich wollte Vektoren für Gleichheit vergleichen, aber Schwimmer Operationen Fehler geben Runden, also wollte ich ungefähre Gleichheit. Lange Rede kurzer Sinn, überwiegendes gleich ist eine schlechte Idee, es sei denn, Ihre Implementierung ist symmetrisch, reflexiv und transitiv.

Andere Klassen werden equals zu übernehmen hat diese Eigenschaften, und so werden Klassen diese Klassen verwenden, und so kann man in seltsamen Fällen enden. Zum Beispiel könnte eine Liste erzwingen Eindeutigkeit, sondern mit zwei Elementen am Ende, die als gleich ein Element B zu bewerten.

Eine Hash-Tabelle ist das perfekte Beispiel für ein unvorhersehbares Verhalten, wenn Sie Gleichheit brechen. Zum Beispiel:

//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!

Ein weiteres Beispiel wäre ein Set:

//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()

Ich schlage vor, eine andere Methode verwenden, mit einem Namen wie ApproxEquals. Sie könnten auch erwägen den Operator == überschreiben, weil es nicht virtuell ist und daher nicht versehentlich von anderen Klassen wie Equals verwendet werden könnte.

Wenn Sie wirklich nicht Verweisgleichheit für die Hash-Tabelle verwenden können, nicht ruinieren die Leistung von Fällen, in denen Sie können. Fügen Sie eine IApproxEquals Schnittstelle implementieren es in Ihrer Klasse, und fügen Sie Wörterbuch eine Erweiterungsmethode GetApprox, die die Schlüssel der Suche nach einer etwa gleich einer aufzählt, und gibt den zugehörigen Wert. Sie könnten auch ein Benutzerwörterbuch schreiben speziell für 3-dimensionale Vektoren, oder was auch immer Sie brauchen.

Answer 2

Wenn es „verstößt gegen den Vertrag von equals“, dann sollte ich bin mir nicht sicher, dass Sie es als Schlüssel verwenden.

Es ist etwas verwendet, das als Schlüssel, die Sie wirklich das Hashing-Recht erhalten müssen ... es ist sehr unklar, was die Equals Logik, sondern zwei Werte, die als gleich betrachtet werden muss haben die gleicher Hash-Code. Es ist nicht erforderlich, dass zwei Werte mit dem gleichen Hash-Code gleich sind.

eine konstante Zeichenkette verwendet wirklich nicht viel helfen - Sie die Werte geteilt gleichmäßig über die Arten erhalten werden, aber das wars auch schon ...

Answer 3

Ich bin gespannt, was die Begründung für das Überschreiben GetHashCode() wäre und einen konstanten Wert zurückkehrt. Warum verletzen die Idee eines Hash und nicht nur den „Vertrag“ zu verletzen und nicht das Überschreiben der GetHashCode() Funktion überhaupt nicht und lassen Sie die Standardimplementierung von Object?

Bearbeiten

Wenn das, was Sie getan haben, ist, dass so können Sie Ihre Objekte auf ihre Inhalte übereinstimmen Basis haben können, anstatt ihre Referenz dann, was Sie vorschlagen, mit verschiedenen Klassen einfach verschiedene Konstanten verwenden können arbeiten, aber ist sehr ineffizient. Was Sie tun möchten, ist mit einem Hash-Algorithmus kommen, die den Inhalt Ihrer Klasse nehmen und einen Wert erzeugen, die Geschwindigkeit gleicht mit gleichmäßiger Verteilung (das Hashing 101).

Ich glaube, ich bin nicht sicher, was Sie suchen ... es nicht ein „gutes“ Schema für die Wahl konstante Zahlen für dieses Paradigma ist. Man ist nicht besser als die andere. Versuchen Sie, Ihre Objekte zu verbessern, so dass Sie einen echten Hash erzeugt wird.

Answer 4

Wenn Hash-Kollisionen auftreten, die HashTable / Dictionary Anrufe Equals den Schlüssel Sie suchen zu finden. einen konstanten Hash-Code entfernt die Geschwindigkeitsvorteile der einen Hash in erster Linie mit -. es eine lineare Suche wird

Sie sagen, die Equals-Methode wird nach nicht umgesetzt worden, um den Vertrag. Was genau meinen Sie damit? Je nach Art der Verletzung wird der HashTable oder Wörterbuch nur langsam (lineare Suche) oder überhaupt nicht funktionieren.