Warum GetHashCode() wichtig ist

Frank Eller    08.07.2017    00:00

Learning

Wenn man eine eigene Klasse erstellt, überschreibt man oftmals die Equals()-Methode, um sicherzustellen dass der Inhalt der Klasse (bzw. des späteren Objekts) bei einem Vergleich herangezogen wird. Equals() ist aber nicht die einzige wichtige Komponente hierbei, genauso wichtig ist GetHashCode(). Deshalb warnt das Visual Studio auch wenn man Equals() überschreibt, GetHashCode() aber nicht. Dieser Post zeigt, warum das unter Umständen wichtig sein kann.

Die Idee zu diesem Post stammt übrigens von meinem Kollegen Robert Großmann, der auch eine erste Version des nun folgenden Benchmarks geschrieben hatte. Ein Benchmark deshalb, weil man daran genau sieht, wenn es ein Performance-Problem geben könnte. In diesem Fall machen wir etwas sehr einfaches: Wir erzeugen ein Dictionary, befüllen es mit einer vorgegebenen Anzahl von Werten, entnehmen diese Werte wieder und messen die Zeit. Die Methode für die Zeitmessung wurde allgemeingültig geschrieben, wir sehen sie hier:

private static TimeSpan CheckDictionary<K>( IList<K> keys )
{
  Dictionary<K, string> dictionary = new Dictionary<K, string>();

  Stopwatch watch = Stopwatch.StartNew();

  foreach ( K key in keys )
  {
    dictionary.Add( key, "Value" );
  }

  foreach ( K key in keys )
  {
    string currentValue = dictionary[key];
  }

  watch.Stop();

  return watch.Elapsed;
}
Die Methode ist sehr einfach gehalten. Ich übergebe hier einfach eine Liste von Keys. In der Methode wird ein Dictionary erzeugt (außerhalb der Zeitmessung), mit dem Typ des Keys und einem String als Wert. Der Wert ist uninteressant für den Benchmark, wir schreiben da also einfach hart immer den gleichen Wert hinein. Die Zeit für das Schreiben und Lesen wird gemessen und das Ergebnis zurück geliefert. die Hauptmethode der Anwendung ist daher ebenfalls denkbar einfach. Für einen ersten Test habe ich einen String als Datentyp für den Dictionary-Schlüssel verwendet.
static void Main( string[] args )
{
  // number of keys
  int[] keyCounts = { 10, 100, 1000, 10000 };

  foreach ( int count in keyCounts )
  {
    List<int> keyIds = Enumerable.Range( 1, count ).ToList();

    List<string> stringKeys = keyIds.Select( k => k.ToString() ).ToList();

    Console.WriteLine( $"Number of keys: {count}" );
    TimeSpan stringKeyTimeSpan = CheckDictionary( stringKeys );

    Console.WriteLine( $"String:\t\t{stringKeyTimeSpan}" );

    Console.WriteLine();
  }
}

Wenn man diesen Code ausführt ergibt sich folgendes Ergebnis:

Eine eigene Klasse als Key

Das erste Element das wir hinzufügen wollen ist die Verwendung einer eigenen Klasse, komplett ohne Überladungen, als Key. Die Klasse ist wie folgt definiert:
public class DefaultKey
{
  public string FirstValue { get; set; }
  public string SecondValue { get; set; }

  public DefaultKey( string firstValue, string secondValue )
  {
    FirstValue = firstValue;
    SecondValue = secondValue;
  }
}
Die Klasse DefaultKey beinhaltet keine Überladung der Vergleichsmethoden (was aber auch bedeutet, dass ein Vergleich zweier Objekte möglicherweise nicht so abläuft wie wir das gerne in der Anwendung hätten). Deshalb ist zu erwarten, dass die Performance ähnlich ist wie bei der String-Variante. Wir erweitern die Main()-Methode um das neue Element.
static void Main( string[] args )
{
  // number of keys
  int[] keyCounts = { 10, 100, 1000, 10000 };

  foreach ( int count in keyCounts )
  {
    List<int> keyIds = Enumerable.Range( 1, count ).ToList();

    List<string> stringKeys = keyIds.Select( k => k.ToString() ).ToList();
    List<DefaultKey> defaultKeys = keyIds.Select( k => new DefaultKey( k.ToString(), k.ToString() ) ).ToList();

    Console.WriteLine( $"Number of keys: {count}" );
    TimeSpan stringKeyTimeSpan = CheckDictionary( stringKeys );
    TimeSpan defaultKeyTimeSpan = CheckDictionary( defaultKeys );

    Console.WriteLine( $"String:\t\t{stringKeyTimeSpan}" );
    Console.WriteLine( $"Default:\t{defaultKeyTimeSpan}" );

    Console.WriteLine();
  }
}

Es sollte kein Problem sein, weitere Key-Varianten hinzuzufügen, im Prinzip bleibt der Code ja identisch. Deshalb werde ich in der Folge die Main()-Methode nicht nochmal posten. Führt man diesen Code aus, ergibt sich ein erwartetes Ergebnis:

Next Step: Überschreiben von Equals

Möchte man sicherstellen, dass der Vergleich zweier Objekte nach der eigenen Vorstellung passiert, überschreibt man die Equals-Methode. Hierzu habe ich eine weitere Key-Klasse erstellt. Allerdings, wie bereits in der Einleitung gesagt, wird das Visual Studio sich beschweren - wenngleich nicht mit einem Error, sondern einer Warning - dass man auch GetHashCode überschreiben sollte. Die Grundregel ist folgende: Wenn gilt a.Equals(b) == true dann muss auch gelten a.GetHashCode().Equals(b.GetHashCode()) == true. Und das kann man nur sicherstellen, indem man GetHashCode() überschreibt.

Es ist allerdings nicht so wahnsinnig einfach, eine sinnvolle GetHashCode()-Implementierung aus dem Hut zu zaubern, weshabl häufig ein Fehler gemacht wird: Man liefert einfahc immer den gleichen Wert zurück. Oder mit anderen Worten: 0. Denn damit ist ja sichergestellt, obige zwei Gleichungen stimmen (da a.GetHashCode() immer gleich b.GetHashCode() ist). Und genau hier liegt das Problem, wie wir gleich sehen werden. Eine entsprechende Implementierung eines Keys sieht so aus:

public class NoHashcodeKey
{
  public string FirstValue { get; set; }
  public string SecondValue { get; set; }

  protected bool Equals( NoHashcodeKey other )
  {
    return string.Equals( FirstValue, other.FirstValue ) && string.Equals( SecondValue, other.SecondValue );
  }

  public override bool Equals( object obj )
  {
    if ( obj == null )
    {
      return false;
    }
    if ( ReferenceEquals( this, obj ) )
    {
      return true;
    }
    if ( obj.GetType() != this.GetType() )
    {
      return false;
    }
    return Equals( (NoHashcodeKey)obj );
  }

  public override int GetHashCode()
  {
    return 0;  // Hashcode not checked
  }

  public NoHashcodeKey( string firstValue, string secondValue )
  {
    FirstValue = firstValue;
    SecondValue = secondValue;
  }
}

Das Ergebnis bei der Ausführung des Codes ist allerdings nicht so schön:



Für 10000 Elemente benötigt das Dictionary jetzt schon ganz 4 Sekunden - im Vergleich zum Millisekundenbereich anderer Implementierungen.

Volle Implementierung

Bedeutet das jetzt, dass man GetHashCode() nicht überschreiben sollte? (Denn wenn man die Methode nicht überschreibt, ergibt sich ein ähnliches Bild wie bei den beiden ersten Varianten). Natürlich nicht. Man sollte GetHashCode() überschreiben, aber sinnvoll. Es gibt Tools, die eine entsprechende Implementierung vorgeben, die man wiederverwenden kann. Der folgende Code zeigt zum Abschluss eine voll implementierte Key-Klasse inklusive GetHashCode().

public class FullKey : IEquatable<FullKey>
{
  public string FirstValue { get; set; }
  public string SecondValue { get; set; }


  public bool Equals( FullKey other )
  {
    if ( other == null )
    {
      return false;
    }
    return String.Equals( FirstValue, other.FirstValue ) && 
      String.Equals( SecondValue, other.SecondValue );
  }

  public override bool Equals( object obj )
  {
    return Equals( obj as FullKey );
  }

  public override int GetHashCode()
  {
    unchecked
    {
      int firstHashCode = FirstValue != null ? FirstValue.GetHashCode() : 0;
      int secondHashCode = SecondValue != null ? SecondValue.GetHashCode() : 0;
      return ( firstHashCode * 397 ) ^ secondHashCode;
    }
  }

  public FullKey( string firstValue, string secondValue )
  {
    FirstValue = firstValue;
    SecondValue = secondValue;
  }
}

Die gezeigte Implementierung ist natürlich nur ein Beispiel - je nachdem wie die Equals-Methode aufgebaut ist, kann es hier Unterschiede geben. Aber sie kann auch als Vorlage dienen. Das Ergebnis dieser Implementierung zeigt die folgende Grafik:

Kommentare

Es gibt noch keine Kommentare für diesen Artikel

Kommentar hinzufügen

5 + 10 =