Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Grundlegendes zu Hashtables
DarkShadow81
myCSharp.de - Member



Dabei seit:
Beiträge: 222
Herkunft: Berlin

Themenstarter:

Grundlegendes zu Hashtables

beantworten | zitieren | melden

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 ) ?
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
DarkShadow81
myCSharp.de - Member



Dabei seit:
Beiträge: 222
Herkunft: Berlin

Themenstarter:

re

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
VizOne
myCSharp.de - Member

Avatar #avatar-1563.gif


Dabei seit:
Beiträge: 1.373

beantworten | zitieren | melden

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

MfG VizOne
private Nachricht | Beiträge des Benutzers
Robert G
myCSharp.de - Member

Avatar #avatar-1907.png


Dabei seit:
Beiträge: 347
Herkunft: München

beantworten | zitieren | melden

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....
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Robert G,
Zitat
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
private Nachricht | Beiträge des Benutzers
Robert G
myCSharp.de - Member

Avatar #avatar-1907.png


Dabei seit:
Beiträge: 347
Herkunft: München

beantworten | zitieren | melden

Zitat
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.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

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.
Zitat
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.
Zitat
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
private Nachricht | Beiträge des Benutzers
VizOne
myCSharp.de - Member

Avatar #avatar-1563.gif


Dabei seit:
Beiträge: 1.373

beantworten | zitieren | melden

Zitat
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:
Zitat
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
private Nachricht | Beiträge des Benutzers