Laden...

[Artikel] Dictionary/HashSet/Hashtable: Grundlegende Informationen

Erstellt von herbivore vor 18 Jahren Letzter Beitrag vor 18 Jahren 45.432 Views
herbivore Themenstarter:in
49.485 Beiträge seit 2005
vor 18 Jahren
[Artikel] Dictionary/HashSet/Hashtable: Grundlegende Informationen

Vorne weg:

In .NET 2.0 gibt es Dictionary <TKey, TValue> das funktional der Hashtable aus .NET 1.1 entspricht, dieser aber wegen der Typsicherheit und zur Vermeidung von Casts unbedingt vorzuziehen ist.

In .NET 3.5 gibt es HashSet <TKey> also quasi ein Dictionary nur mit Key, aber ohne Value. Dies ist in allen Beispielen vorzuziehen, in denen das Value nicht benötigt wird.

Die Hashtable-Klasse sollte also nicht mehr verwendet werden, sondern immer durch Dictionary oder HashSet ersetzt werden. ArrayList gehört genauso in die Mottenkiste und sollte - wie generell alle untypisierten Collections aus System.Collections - nicht mehr benutzt, sondern durch List<T> ersetzt werden.

Hashtables sind vielfältig einsetzbar!

Kleiner Ausflug: Perl verdankt seine Leistungsfähigkeit (neben dem guten Support für Regular Expressions) zu einem großen Teil der Tatsache, es Hashtables genauso einfach und selbstverständlich unterstützt wie Arrays. Nicht umsonst sagt der Vater von Perl, Larry Wall, das jemand, der keine Hashes benutzt, noch nicht wirklich Perl programmiert.

Leider werden Hashtables in C# nicht genauso gut unterstützt wie in Perl. Aber extrem nützlich bleiben sie trotzdem.

Hashtables als Listen mit Strings als Index

Im ersten Ansatz ist eine Hashtable einfach eine ArrayList, deren Index ein String statt einem Integer ist.

Nehmen wir an, wir hätten folgende Klasse:


public class MyClass
{
   private int _iId;

   private static ArrayList _alAlleObjekte = new ArrayList ();

   public MyClass (int iId)
   {
      _iId = iId;
      _alAlleObjekte [_iId] = this;
   }

   public static MyClass GibObjektZuId (int iId)
   {
      return (MyClass)_alAlleObjekte [iId];
   }
}

Wenn die Ids stattdessen Strings wären, nehmen wir einfach eine Hashtable:


public class MyClass
{
   private String _strId;

   private static Hashtable _htAlleObjekte = new Hashtable ();

   public MyClass (String strId)
   {
      _strId = strId;
      _htAlleObjekte [_strId] = this;
   }

   public static MyClass GibObjektZuId (String strId)
   {
      return (MyClass)_htAlleObjekte [strId];
   }
}

Hashtables als Listen mit nicht numerischen Index

Im zweiten Ansatz fällt uns auf, dass die Keys einer Hashtable nicht nur Strings, sondern beliebige Objekte sein dürfen - vorausgesetzt, sie erfüllen die in der SDK-/MSDN-Doku von GetHashCode genannten Bedingungen und werden nicht geändert, solange sie als Key verwendet werden. Objekte, die sich gar nicht erst ändern können, wie z.B. String, eignen sich natürlich am besten.

Hashtables als schwach besetzte (sparse) Liste mit numerischen Index

Kommen wir nochmal zur ersten Klasse zurück. Wenn der Benutzer der Klasse die Ids nicht bei eins beginnen lässt, sondern z.B. bei 1.000.000 würde die ArrayList Speicher für eine Million ungenutzter Einträge verbrauchen. Würde man stattdessen auch hier eine


public class MyClass
{
   private int _iId;

   private static Hashtable _htAlleObjekte = new Hashtable ();

   public MyClass (int iId)
   {
      _iId = iId;
      _htAlleObjekte [_iId] = this;
   }

   public static MyClass GibObjektZuId (int iId)
   {
      return (MyClass)_htAlleObjekte [iId];
   }
}

Hashtable verwenden, braucht man nur den Speicher für die tatsächlich enthaltenen Einträge (ok, auf Grund der internen Verwaltung eine Hashtable benötigt man ungefähr doppelt soviel und zusätzlich den Speicher für die geboxten Index-Objekte).

Wenn man das verallgemeinert kann man Hashtables statt ArrayLists immer verwenden, wenn die Arrays nur schwach besetzt sind (sparse arrays). Wenn man in einem Array z.B. nur die folgenden drei Werte speichern will, fährt man mit einer Hashtable deutlich besser als mit einer ArrayList:


a [5] = 97;
a [8798] = 97;
a [9979679] = 97;

Hashtables als Mengen

In .NET 3.5 gibt es HashSet <TKey> also quasi eine Hashtable nur mit Key, aber ohne Value. Wenn man mit Mengen arbeiten will, sollte man HashSet verwenden.

Aber das sind immer noch nicht die richtigen Knaller. Wenn man Hashtables als Mengen von Objekten betrachtet, fängt es an, interessant zu werden. Dazu muss man insofern umdenken, als dass jetzt die eigentlichen Informationen in den Schlüsseln gespeichert werden und die Werte egal sind.

Einige Suchmaschinen entfernen z.B. vor der Indexierung überflüssige Allerweltswörter (der, die, das, ein, eine, ...). Nehmen wir mal an, wir haben schon alle Wörter des zu indexierenden Textes in astrWords, dann kann man die Allerweltswörter als Schlüssel einer Hashtable speichern und per Contains-Methode sehr effektiv feststellen, ob eine Wort in der Menge der Allerweltswörter enthalten ist.


htSkip ["der"] = true;
htSkip ["die"] = true;
//...
foreach (String strWord in astrWords) {
   if (ht.Contains (strWord)) {
      continue;
   }
   // Indexierung
}

Man kann mit Hashtables weiterhin sehr einfach die Mengenoperationen Vereinigungsmenge, Schnittmenge u.ä. nachbilden. Einer Verwendung von Hashtables als Mengen i. Allgemeinen steht also nichts entgegen.

Hashtables als attributierte Mengen (hier: Worthäufigkeiten)

Da die Objekte einer Menge in den Schlüsseln der Hashtable gespeichert sind, können wir natürlich mit den Werten der Hashtable mehr anstellen, als angeben, dass das Objekt in der Menge ist (deshalb oben auch 'true'). Im folgenden Beispiel, wird die Häufigkeit der Wörter in einem Text gezählt. Gehen wir mal davon aus, dass die Wörter bereits wieder in astrWords enthalten sind:


foreach (String strWord in astrWords) {
   if (!ht.Contains (strWord)) {
      ht [strWord] = 1;
   } else {
      ht [strWord] = ((int)ht [strWord]) + 1;
   }
}

Gucken wir uns noch schnell an, wie man die Wörter und ihre Häufigkeiten sortiert ausgibt:


String [] astrWords = new String [ht.Keys.Count];
ht.Keys.CopyTo (astrWords, 0);
Array.Sort (astrWords);
foreach (String strWord in astrWords)
{
   Console.WriteLine ("{0,-20} = {1,3}", strWord, ht[strWord]);
}

Hashtables zur schnellen Prüfung auf Enthaltensein

Ein wichtiger Punkt fehlt bis jetzt noch, nämlich dass der Zugriff auf eine Hashtable per Key (i.d.R.) nur einen konstanten Aufwand verursacht, egal wieviele Elementen in der Hashtable enthalten sind. Wenn man also in dem obigen Beispiel


htSkip ["der"] = true;
htSkip ["die"] = true;
//...
foreach (String strWord in astrWords) {
   if (ht.Contains (strWord)) {
      continue;
   }
   // Indexierung
}

mit Contains fragt, ob ein Wort schon enthalten ist, muss nicht wie bei einer Liste Element für Element durchsucht werden, ob es schon vorhanden ist - das wäre linearer Aufwand. Es ist nicht mal wie bei sortierten Listen nötig eine binäre Suche durchzuführen, die immerhin noch logarithmischen Aufwand hätte. Nein, die Hashtable entscheidet (i.d.R.) direkt an Hand des Elements: ist drin oder nicht. Also konstante Zeit, auch bei Millionen und Abermillionen Einträgen. Das ist ein nicht zu unterschätzender Vorteil, inbesondere bei der Verarbeitung großer Datenmengen.

Weitere Anwendungsmöglichkeiten von Hashtables

Das soll erstmal mein letztes Beispiel gewesen sein, obwohl man mit Hashtables natürlich noch weit mehr anstellen kann.

Wenn man selbst weitere Anwendungsmöglichkeiten sucht, sollte man immer beachten, dass man die Möglichkeit hat, die "eigentliche" Information 1) in den Schlüsseln, 2) in den Werten oder eben 3) im Zusammenspiel von Schlüssen und Werten speichern kann.

Die Anwendungsmöglichkeiten sind nahezu unbegrenzt und wenn man erstmal auf den Geschmack gekommen ist, wird man Hashtables nicht mehr missen wollen.

Originalthread: Link