Laden...

Grundlegendes zu Hashtables

Erstellt von DarkShadow81 vor 19 Jahren Letzter Beitrag vor 17 Jahren 10.124 Views
D
DarkShadow81 Themenstarter:in
222 Beiträge seit 2004
vor 19 Jahren
Grundlegendes zu Hashtables

hi, hab jetzt schon einiges gelesen hier über Hashtables, und das sie wohl sehr schnell und effektiv seien. Nur frag ich mich, wo liegt die effektive Anwendung darin bzw wo kann man sie wirklich gut einsetzen (auch vom Code her ) ?

49.485 Beiträge seit 2005
vor 19 Jahren

Hallo DarkShadow81,

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.

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];
   }
}

Im zweiten Ansatz fällt uns auf, dass die Keys einer Hashtable nicht nur Strings, sondern beliebige Objekte sein dürfen.

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;

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 Allerweltsworte (der, die, das, ein, eine, ...). Nehmen wir mal an, wir haben schon alle Worte des zu indexierenden Textes in astrWords, dann kann man die Allerweltsworte als Schlüssel einer Hashtable speichern und per Contains-Methode sehr effektiv feststellen, ob eine Wort in der Menge der Allerweltsworte 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.

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 Worte in einem Text gezählt. Gehen wir mal davon aus, dass die Worte 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 Worte 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]);
}

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.

HTH

herbivore

D
DarkShadow81 Themenstarter:in
222 Beiträge seit 2004
vor 19 Jahren
re

ich danke dir für die ausführliche Darstellung. Werd es mir in Ruhe zu gemüte führen und durchtesten. Hoffe ich kann noch Rückfragen stellen, da bestimmt noch einiges offen sein wird von meiner Seite

1.373 Beiträge seit 2004
vor 19 Jahren

Sehr interessant für Datenstrukturen im Allgemeinen und Hashtables im Speziellen:
Datenstrukturen (.NET 1.1)
Datenstrukturen (.NET 2.0)

MfG VizOne

347 Beiträge seit 2006
vor 17 Jahren

Ich bin gerade zufällig über die FAQ zu dem Thread gekommen.

Auch wenn das jetzt etwas kleinkariert wirken mag, die Erklärungen in den FAQ sind nicht richtig und der Leser bekommt einen komplett falschen Eindruck von Dictionaries bzw. normalen array-/listenbasierten Containern.

Eine HashTable hat den Vorteil, dass sie nicht suchen muss um etwas zu finden.
Aus dem Hash des Schlüssels berechnet sich seine Position in der internen Datenstruktur. Das heißt wenn ich ein Dictionary<string, XXX> habe wird eine Suche á la:

XXX element;
if(dictionary.TryGetValue("Hallo", out element))
  gefunden!

Bei 10 Elementen genauso lange dauern wie bei 10 Mio Elementen.
Um in einem normalen Container effizient suchen zu können müsste man diesen erst sortieren. Aber selbst eine Binrarysearch ist verglichen zu einer HashTable ziemlich langsam. Wobei natürlich die Generierung des HashCodes aus "Hallo" schneller als bei einer 20MB Datei als Schlüssel passiert. 😁
Ein wenig relativieren muss man also schon. 😉

Vielleicht reicht das als kleine Anregung für den FAQ Artikel....

49.485 Beiträge seit 2005
vor 17 Jahren

Hallo Robert G,

die Erklärungen in den FAQ sind nicht richtig

was ist deiner Meinung nach nicht richtig?

Was du über die Funktionsweise von Hashtables geschrieben hast, ist sicher richtig. Das war und ist mit bekannt, aber mir war es wichtiger zu beschreiben, wie man Hashtables verwendet. BTW: Der Titel "Grundlegendes zu Hashtables" ist nicht von mir.

herbivore

347 Beiträge seit 2006
vor 17 Jahren

was ist deiner Meinung nach nicht richtig? HashTabellen werden da wie normale Container erklärt.
Ich finde man sollte hier nicht auf ein so tiefes Level herabsteigen. Ein Anfänger hat ganz andere Probleme als die Wahl des optimalsten Contaiiners.
Ein Umsteiger von einer nativen Sprache wie C/C++, D, ADA oder Delphi könnte sicher mit den Begriffen etwas anfangen und würde sich über ein paar Infos zu den Pros und Contras der .Net Implementierung freuen.

Vllt wäre deshalb ein weiterführender Artikel ganz nett. Der zum Beispiel TreeSet und Dictionary vergleicht, damit der Leser sich das richtige Werkzeug für seine Aufgabe wählen kann.
Da du oben Megenoperationen erwähnt hast: Ich habe an einer Implementierung von PascalSets für .Net mitgebastelt. Du findest es hier. Ist vllt auch interessant. 😉

49.485 Beiträge seit 2005
vor 17 Jahren

Hallo Robert G,

eine Hashtabelle ist ein ganz normaler Container. Und jede Container-Implementierung (Array, LinkedList, SortedList, Hashtable, ...) hat so ihre eigenen Eigenschaften, auch und gerade was die Aufwände für die einzelnen Operationen angeht.

Ich finde man sollte hier nicht auf ein so tiefes Level herabsteigen.

Ich mache genau das Gegenteil, in dem ich eben nicht auf die Implementierung eingehe und nur die Verwendung beschreibe.

Ein Anfänger hat ganz andere Probleme als die Wahl des optimalsten Contaiiners.

Ich finde, spätestens jetzt fängst du an, dir zu widersprechen.

Sorry, insgesamt kann ich mit deine Kritik (insbesondere so absolut forumliert) nicht wirklich was anfangen. Dein Hinweis mit den konstanten Zugriffszeiten war sicher hilfreich. Vielleicht können wir das so stehen lassen.

herbivore

1.373 Beiträge seit 2004
vor 17 Jahren

Original von Robert G
Eine HashTable hat den Vorteil, dass sie nicht suchen muss um etwas zu finden.

Das ist nicht wahr. Auch in einer Hashtable muss noch gesucht werden mit mindestens einem (1) Objekt-Vergleich. Im Falle einer Kollision kann das Suchen - abhängig von der verwendeten Kollisionsauflösung - aufwändiger sein als O(1), bis hin zu O(n).

http://de.wikipedia.org/wiki/Suchen sagt:

Suchen ist die Tätigkeit oder der Versuch, ein Ding nach bestimmten Kriterien zu finden. Dabei ist zu unterscheiden, ob der Ort eines bestimmten Objektes gesucht wird (aufsuchen), oder ob eine Menge von Objekten gefunden werden soll, die gewissen Kriterien entsprechen (zusammensuchen).

Grüße,
Andre