Aus der MSDN-Entwickler-Hotline: Wie implementiert man die GetHashCode()-Methode für ein Objekt mit zwei Integern?

Question

Hallo zusammen,

heute wurde uns bei der MSDN-Entwickler-Hotline unter anderem folgende Frage gestellt:

Wie implementiert man die GetHashCode()-Methode für ein Objekt mit zwei Integern?

Unsere Antwort bzw. unser Lösungsvorschlag darauf war:

Wenn die beiden Integer-Variabeln den vollen Bereich zwischen int.MinValue und int.MaxValue abdecken können ist es nicht möglich eine perfekte Hash-Funktion für ein solches Objekt zu schreiben. Das ist aber auch nicht nötig.

Am wichtigsten ist zunächst, dass zwei Objekte, deren Werte übereinstimmen denselben HashCode zurückliefern. Eine weitere Anforderung an die Hash-Funktion sollte sein, dass Sie möglichst wenige Kollisionen enthält. Andernfalls kann die Performance Ihrer Anwendung eingeschränkt werden.

Folgendes Beispiel soll dies verdeutlichen. Wir betrachten folgende Klasse, deren Werte a und b im Bereich (0...1000) liegen:

public class MyTuple
{
	public static int CollisionCounter { get; set; }

	private int a;
	private int b;
	public MyTuple(int a, int b)
	{
		this.a = a;
		this.b = b;
	}
}

Wir betrachten 3 Implementierungen von der GetHashCode()-Funktion:

// a
public override int GetHashCode()
{
    return a + b;
}

// b
public override int GetHashCode()
{
    return a * 31 + b;
}

// c
public override int GetHashCode()
{
    return a * 10000 + b;
}

Jetzt fügen wir 100000 MyTuple-Objekte in ein HashSet ein und messen die Zeit und die Anzahl der Kollisionen:

a) 117ms 3.107.806

b) 32ms 144.540

c) 11ms 0

Für das gegebene Szenario ist die letzte Version die beste, da es nachweislich nicht zu Kollisionen kommen kann. Gute Werte liefert auch die zweite Version. Diese multipliziert einen Wert mit der Primzahl 31 und addiert den zweiten dazu. Dabei kommmt es ebenfalls zu einer guten Performance. Diese Version eignet sich vor allem auch, wenn keine Informationen über den Wertebereich vorliegen. Unter [1] finden Sie einen Blog-Eintrag, der sich mit dem Erstellen einer guten Hash-Funktion beschäftigt.

[1] Guidelines and rules for GetHashCode

Wir hoffen, vielen Besuchern der MSDN Foren durch das Posten dieses Problems und einer möglichen Lösung weiterhelfen zu können.

Viele Grüße,
Thomas Fröhle
Entwickler-Hotline für MSDN Online Deutschland

Disclaimer:
Bitte haben Sie Verständnis dafür, dass wir hier auf Rückfragen gar nicht oder nur sehr zeitverzögert antworten können.
Bitte nutzen Sie für Rückfragen oder neue Fragen den telefonischen Weg über die MSDN-Entwickler-Hotline: http://www.msdn-online.de/Hotline


Es gelten für die MSDN-Entwickler-Hotline und dieses Posting diese Nutzungsbedingungen, Hinweise zu Markenzeichen, Informationen zur Datensicherheit sowie die gesonderten Nutzungsbedingungen für die MSDN-Entwickler-Hotline.