Spaß mit GetHashCode() oder wie man ein Dictionary verwirrt

Möchte man sehr eigenartige und kaum nachvollziehbare Seiteneffekte vermeiden, so sollte man tunlichst darauf achten, dass die Schlüsselklasse eines Dictionary unveränderlich ist, wie etwa Dictionary<string, …> oder Dictionary<int, …>. Aber eigentlich tut es doch jede Klasse, die vernünftig GetHashCode() und Equals() unterstützt, oder?

Nehmen wir einmal eine solche Klasse:

class ChangableNumber
{
public int Number { get; set; }
public override int GetHashCode()
{
return Number.GetHashCode();
}
public override bool Equals( object obj )
{
ChangableNumber other = obj as ChangableNumber;
if (null == other) return false;
return (Number == other.Number);
}
}

Und bauen uns ein Dictionary mit einem Schlüssel, den wir verändern. Was erzeugt wohl das folgende Programm als Ausgabe:

ChangableNumber c1 = new ChangableNumber { Number = 1 };
Dictionary dict = new Dictionary();
dict[c1] = true;
Console.WriteLine( dict.ContainsKey( c1 ) );
c1.Number = 4;
Console.WriteLine( dict.ContainsKey( c1 ) );
c1.Number = 1;
Console.WriteLine( dict.ContainsKey( c1 ) );

Nun, erst mal wie erwartet: true (1 ist drin), false (4 natürlich nicht) und true (1 ist wieder drin). Was aber, wenn GetHashCode() zufälligerweise für den veränderten Wert den selben Schlüssel liefert (respektive dieser versehen mit dem Modulo des Dictonary den selben Wert hat)? Das ist einfach zu testen: der Inhalt von GetHashCode() wird durch return 1; ersetzt. Nun ist das Ergebnis true, true und wieder true. Wie kommt die 4 denn nun in das Dictionary?

Der Trick ist einfach: ein Dictionary nimmt den Wert von GetHashCode() und ermittelt daraus zum Beispiel durch ein Modulo (mit einer Primzahl, muss aber nicht) einen Indexwert. Für jeden Indexwert wird eine Liste von Schlüssel / Wert [interessiert hier nicht] Paaren verwaltet, i.e. eine Liste enthält alle Schlüssel, die aus Sicht des Dictionary den gleichen Hash haben.

Im ersten Beispiel waren diese (zufällig) unterschiedlich, so dass das Dictionary beim Anlegen eine Liste (sagen wir mal 1) mit einem Schlüssel / Wert Paar anlegte. Das Ändern in 4 führt dazu, dass bei der Prüfung mittels ContainsKey eine nicht vorhandene Liste (4 oder was auch immer) gesucht wird. Diese ist leer, also liefert ContainsKey false.

Im zweiten Beispiel wird nach der Änderung aber die (immer einzige) Liste (1) untersucht. Diese ist nun nicht leer, so dass alle Schlüssel mittels Equals verglichen werden. Natürlich passt unser Schlüssel nun immer, da er mit sich selbst verglichen wird (i.e. in diesem Beispiel kann man jeden beliebigen Wert zuweisen, das zweite ContainsKey ist immer true). Für das ursprüngliche Beispiel wäre übrigens -2147483647 (0x80000001) der zugehörige Killerwert – vermutlich der einzige.

Und das Fazit? Veränderliche Schlüssel für ein Dictionary sollten nur mit vorherigem Nachdenken verwendet werden.

Viel Glück dabei

Jochen

Bookmark the permalink.

Schreibe einen Kommentar