GetHashCode und Equals: Warum ihre Überschreibung für C# entscheidend ist

Einleitung: Der Fehler, der Ihren Code verlangsamt

Jeder, der schon einmal in C# programmiert und mit Dictionary oder HashSet gearbeitet hat, stößt früher oder später auf diese Frage auf Stack Overflow. Tausende von Aufrufen, Dutzende von Antworten, aber der Kern ist derselbe: Wenn Sie Equals in Ihrer Klasse überschrieben, aber GetHashCode vergessen haben – kann Ihr Code falsch oder extrem langsam funktionieren. Warum? Lassen Sie es uns anhand realer Beispiele verstehen.

Stellen Sie sich vor, Sie schreiben ein Buchungssystem für Flugtickets. Sie haben eine Klasse Flight mit einer eindeutigen Flugnummer und einem Datum. Sie möchten diese Klasse als Schlüssel in einem Dictionary verwenden. Es scheint einfach. Aber ohne das richtige GetHashCode kann Ihr Wörterbuch zu einer entarteten Liste mit einer Suchgeschwindigkeit von O(n) statt O(1) werden.

Die Magie von Hash-Tabellen: Wie Dictionary in C# funktioniert

Um das Problem zu verstehen, müssen wir unter die Haube von Dictionary schauen. Im Inneren handelt es sich um ein Array von "Buckets". Wenn Sie ein Element hinzufügen, ruft C# die Methode GetHashCode() des Schlüssels auf, um die Bucket-Nummer zu bestimmen. Wenn sich bereits Elemente im Bucket befinden, wird Equals() aufgerufen, um mit jedem von ihnen zu vergleichen. Genau dieses Zusammenspiel sorgt für blitzschnelle Suchvorgänge.

Der Vertrag, der nicht verletzt werden darf

In C# gibt es einen ungeschriebenen, aber strengen Vertrag:

\n
• Wenn Equals() für zwei Objekte true zurückgibt, müssen ihre Hashcodes gleich sein.
\n
• Wenn die Hashcodes unterschiedlich sind, wird Equals() niemals aufgerufen (dies ist eine Optimierung).
\n
• Das Gegenteil ist nicht zwingend erforderlich: Unterschiedliche Objekte können denselben Hashcode haben (Kollision).
\n

Wenn Sie nur Equals überschreiben, aber nicht GetHashCode, erben Sie die Implementierung von System.Object, die auf einem Speicherverweis basiert. Zwei nach Ihrer Logik "gleiche" Objekte haben unterschiedliche Hashcodes. Und hier beginnt das Chaos.

Beispiel für ein Problem: Flüge, die im Wörterbuch verloren gingen

Sehen Sie sich diesen Code an. Es scheint, als sollte er funktionieren, aber er tut es nicht:

public class Flight\n{\n    public string FlightNumber { get; }\n    public DateTime Date { get; }\n\n    public Flight(string flightNumber, DateTime date)\n    {\n        FlightNumber = flightNumber;\n        Date = date;\n    }\n\n    public override bool Equals(object obj)\n    {\n        if (obj is Flight other)\n            return FlightNumber == other.FlightNumber && Date == other.Date;\n        return false;\n    }\n    \n    // GetHashCode NICHT überschrieben!\n}\n\n// Verwendung\nvar flights = new Dictionary<Flight, string>();\nvar f1 = new Flight("SU100", new DateTime(2024, 12, 25));\nvar f2 = new Flight("SU100", new DateTime(2024, 12, 25));\n\nflights[f1] = "Moskau - Paris";\n\n// Fehler! f2 wird nicht gefunden, obwohl f1.Equals(f2) == true\nConsole.WriteLine(flights.ContainsKey(f2)); // False

Warum ist das so? f1 und f2 sind unterschiedliche Objekte im Speicher. Sie haben unterschiedliche Hashcodes von Object.GetHashCode(). Das Wörterbuch legt f1 in Bucket Nr. 123 ab und sucht f2 in Bucket Nr. 456. Equals wird nicht einmal aufgerufen! Das Ergebnis – das Element wird nicht gefunden.

Leistungsproblem: Wenn alles funktioniert, aber langsam

Noch schlimmer ist eine Teillösung. Angenommen, Sie haben GetHashCode überschrieben, aber schlecht gemacht, z. B. eine Konstante zurückgegeben:

public override int GetHashCode() => 42; // Alle Objekte in einen Bucket

Formal ist der Vertrag eingehalten (gleiche Objekte haben denselben Hash). Aber die Leistung bricht ein: Alle Objekte landen in einem Bucket, und das Dictionary entartet zu einer Liste. Einfügen und Suchen werden zu O(n). Für ein Wörterbuch mit 10.000 Elementen ist das eine Katastrophe.

Wie überschreibt man GetHashCode richtig?