Dictionary oder Hashtable

Motivation

In einigen Programmiersprachen ist der Einsatz von Hashtabellen (oder auch assoziativen Arrays) Gang und Gäbe. So zum Beispiel in Perl oder PHP. In C# existiert diese Datenstruktur selbstverständlich auch, jedoch existiert eine generisch typisierte Alternative zu den "normalen" Hashtabellen, das Dictionary.
Doch welche dieser beiden Implementierungen ist vorzuziehen?
Die msdn-Dokumentation (msdn: Hashtable-Auflistungstyp und Dictionary-Auflistungstyp) gibt hierzu leider nur wenig Auskunft, lediglich bei Werttypen soll ein Dictionary leistungsfähiger sein. Der Artikel legt die Vermutung nahe, dass bis auf die Typisierung und ein wenig syntaktischer Zucker (wie TryGetValue) beide Implementierungen ziemlich identisch sind.

Was ist eigentlich eine Hashtabelle?

Eine Hashtabelle wird oft mit Eimern (Buckets) verglichen. Da ich viel bei einem schwedischen Möbelhaus einkaufe, würde ich eher einen Vergleich mit dem Ikea-Lager vorziehen. Grundsätzlich besteht eine Hashtabelle immer aus Schlüssel-Wert-Paaren, anhand eines Schlüssels kann man in einer Hashtabelle ziemlich schnell (konstante Zeit) einen Wert nachschlagen.

Kommen wir zu dem Vergleich mit dem Möbellager, hier wäre der Schlüssel das aufgebaute Möbel, so wie wir es in der Möbelausstellung sehen. Der Wert, den wir jedoch im Möbellager erhalten wollen (oder sollen), ist der zugehörige Bausatz. Im Möbellager müssen wir nun, nachdem wir uns für ein bestimmtes Möbel entschieden haben, den zugehörigen Bausatz suchen, sondern verwenden eine Lagerplatznummer. Dadurch wird jedem Möbel ein eindeutiger Lagerplatz zugewiesen. In der Informatik ist diese Abbildung die Hashfunktion, bei Ikea wird es dafür keine mathematische Formel geben, sondern vielmehr ein Fakturierungsprogramm, dass die Abbildung durchführt.
                    f: Möbel -> Lagerplatz

Testparameter

Um diesen Test durchzuführen, habe ich ein kleines Programm geschrieben, welches Keys und Values jeweils als Strings variabler Länge erzeugt (zwischen 10 und 100 Zeichen). Bei der Suche betrachte ich 2 Szenarien, zum einen die Option, dass jeder Suchschlüssel auch in der Hashtable vorkommt, und zum Anderen, die Option, die wohl am Häufigsten in der Paxis auftaucht: Es existieren etwa 50% der Schlüssel, nach denen gesucht wird.

Test 1: Einfügen von Schlüssel-Wert-Paaren

Beim Einfügen gibt es einen klaren Sieger: das Dictionary, bei großen Datensätzen (ca. 1.000.000) ergibt sich ein Vorteil von ca. 35 %, bei kleineren Tabellen, soger ein Vorteil von bis zu 50 %.

Test 2: Suchen von Schlüsseln

Hier ist das Ergebnis nicht ganz klar, bei großen Datensätzen gewinnt hier die Hashtable mit knapp 6 %. Bei kleinen Testmengen liegt der Vorteil jedoch bei dem Dictionary (ca. 8 %)

Während sich die Nachschlagezeiten in der Hashtable nach vorhandenen und nicht vorhandenen Schlüsseln die Waage hält, ist das Dictionary sogar noch um ca. 3 % schneller, wenn die Hälfte der Schlüssel nicht im Dictionary enthalten sind.

Tipp

Bei der Verwendung des Dictionary ist mit aufgefallen, dass es nur einen Vorteil gibt, wenn man anstatt des vorherigen Prüfens (mittels ContainsKey) mit der Funktion TryGetValue arbeitet:

if (testDictionary.ContainsKey(keyToFind))
    valueFound = testDictionary[keyToFind];

// Besser:

string valueFound = string.Empty;
testDictionary.TryGetValue(keyToFind, out valueFound);

Fazit

Nimmt man die Testergebnisse her, so überwiegt der <u>Vorteil bei dem Dictionary</u>. Dem zugegebener Maßen geringen Performance-Vorteile der Hashtable beim Suchen in großen Datensätzen, steht ein eindeutig besserer Programmierstil, durch die Verwendung von Dictionaries, gegenüber.<br /> <br /></body>