Wie implementiert man eine kompatible GetHashCode-Methode, wenn der Speicherplatz größer als 32 Bits ist?

Question

In .NET müssen Sie, dass Equals (Objekt) und GetHashCode() kompatibel sind. Aber manchmal kann man nicht:

public class GreaterThan32Bits 
{ 
    public int X { get; set; } 
    public int Y { get; set; } 
} 

Da die Datendichte von mehr als 32 Bits ist, und GetHashCode gibt einen Int32, erhalten Sie 3 Lösungen haben (vorausgesetzt, ein korrekt implementiert GetHashCode):

1. vermeiden Code-Duplizierung als falsch

   verworfen

   public override bool Equals(object other) 
   { 
       if(ReferenceEquals(null, other)) return false; 
       if(ReferenceEquals(this, other)) return true; 
       return this.GetHashCode() == other.GetHashCode(); 
   } 
   

2. Implementieren Gleich getrennt von GetHashCode()

   public override bool Equals(object obj) 
   { 
       if(ReferenceEquals(null, other)) return false; 
       if(ReferenceEquals(this, other)) return true; 
       var other = obj as GreaterThan32Bits; 
       if(this.X == other.X) return this.Y == other.Y; 
       return false; 
   } 
   

3. eine größere Präzision GetHashCode64 Implement, die overrided GetHashCode (32 Bits) wird zurückkehren (int) GetHashCode64() und equals kehrt this.GetHashCode64() == anderer .GetHashCode64()

Welchen würden Sie implementieren?

Die erste Lösung ist ungenau falsch, aber sauberer. Die zweite Option scheint sauber zu sein, wird aber sehr komplex, wenn die Klasse mehr Eigenschaften hat. Die dritte Option ist ein Kompromiss.

Answer 1

Ich denke, der Schlüssel, den Sie verpassen, ist, dass GetHashCode() keine eindeutigen Werte zurückgeben muss.

Es ist vollkommen akzeptabel für zwei verschiedene Objekte denselben GetHashCode zurückzugeben. Angenommen, Sie fügen zwei Objekte zu einem HashSet hinzu, die den gleichen HashCode haben, dann wird der Container zuerst den GetHashCode verwenden, um ungefähr im HashSet das Objekt zu finden, und dann das Equals aller übereinstimmenden Objekte, um Ihr genaues Objekt zu finden.

Offensichtlich ist es besser, wenn jedes Objekt einen eindeutigen Hash-Code hat. Wenn jedes Objekt denselben hashCode zurückgibt, wäre die Leistung schrecklich.

Answer 2

Ihre erste Implementierung ist nicht korrekt. Der Hash-Code von zwei Objekten kann gleich sein, obwohl die Objekte selbst nicht gleich sind: Dies ist die Essenz eines Hash-Codes.

Ein Objekt Hash-Code kann zur Bestimmung nützlich sein, wenn zwei Objekte nicht gleich sind, sondern, um zu bestimmen, ob sie sind gleich werden Sie .Equals() verlangen.

Eine Implementierung, die immer 0 für GetHashCode() zurückgibt, ist zulässig, aber möglicherweise nicht sehr effizient, wenn Objekte dieses Typs in verschiedene Containertypen eingefügt werden.

Ihre Option 2 ist die beste Wahl. Es ist eine gute Idee, die Implementierung von Equals() von GetHashCode() getrennt zu halten, weil sie ganz andere Dinge tun. Equals() muss genau dann true zurückgeben, wenn die beiden Objekte in jeder Hinsicht gleich sind. Dazu müssen Sie normalerweise jede Objekteigenschaft einzeln überprüfen.

Answer 3

Genau genommen funktioniert die erste Lösung nicht. Es ist dann keine Lösung.

Die Idee des Hashing ist ganz anders. Int32 ist ziemlich genug für diese Zwecke.

Die vorgeschlagene GetHashCode() ist

return X^Y; 

einfach wie es ist.

BEARBEITEN: Gleichwertige Methoden können dann GetHashCode() verwenden, aber nur false zurückgeben, wenn sich die Hashwerte unterscheiden. Ein tiefer Vergleich ist ohnehin erforderlich.

Answer 4

Die Anforderung lautet wie folgt: if (a.Equals (b)), dann a.GetHashCode() == b.GetHashCode()

Nicht umgekehrt.

Sie sollten Equals() in GetHashCode() nie implementieren. Für GetHashCode gibt es durchaus Kollisionen, aber Equals() darf keine False Positives liefern.

ich diese Implementierung würde vorschlagen:

public override int GetHashCode() 
{ 
    return unchecked(this.X * p1 + this.Y * p2); 
} 

public override bool Equals(object obj) 
{ 
    var other = obj as GreaterThan32Bits; 
    // you must do the null test after the cast, otherwise the 
    // function crashes when obj is not a GreaterThan32Bits instance 
    if (ReferenceEquals(other, null)) return false; 
    return this.X == other.X && this.Y == other.Y; 
} 

Wo p1 und p2 große Primzahlen sind. Dies führt normalerweise zu einer guten Hash-Funktion (wenige Hash-Kollisionen -> Dictionary wird effizient). Wenn die X- und Y-Werte unabhängig sind (zum Beispiel erwarten Sie nicht viele Punkte auf einer geraden Linie wie X = Y), dann kann sogar etwas Einfaches wie X^Y eine gute Hash-Funktion sein.

Aber Sie brauchen nur eine gute Hash-Funktion, wenn Sie die Klasse tatsächlich als Schlüssel in einem Dictionary (oder einer anderen Hash-Tabelle) verwenden.

In der Tat ist es völlig in Ordnung, immer 0 in GetHashCode() zurückgeben und nur Equals() implementieren. Wörterbuch funktioniert immer noch korrekt mit solchen Objekten wie Schlüsseln, es wird nur ineffizient sein.