myCSharp.de - DIE C# und .NET Community
Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 
 | Suche | FAQ

» Hauptmenü
myCSharp.de
» Startseite
» Forum
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Suche
» Regeln
» Wie poste ich richtig?
» Forum-FAQ

Mitglieder
» Liste / Suche
» Wer ist wo online?

Ressourcen
» openbook: Visual C#
» openbook: OO
» Microsoft Docs

Team
» Kontakt
» Übersicht
» Wir über uns

» myCSharp.de Diskussionsforum
Du befindest Dich hier: Community-Index » Diskussionsforum » Entwicklung » Basistechnologien und allgemeine .NET-Klassen » Grundlegendes zu Hashtables
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | Thema zu Favoriten hinzufügen

Antwort erstellen
Zum Ende der Seite springen  

Grundlegendes zu Hashtables

 
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
DarkShadow81 DarkShadow81 ist männlich
myCSharp.de-Mitglied

Dabei seit: 22.10.2004
Beiträge: 222
Entwicklungsumgebung: VS 03,05,mcs,gmcs
Herkunft: Berlin


DarkShadow81 ist offline

Grundlegendes zu Hashtables

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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 ) ?
27.02.2005 14:00 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
herbivore
myCSharp.de-Poweruser/ Experte

avatar-2627.gif


Dabei seit: 11.01.2005
Beiträge: 49.473
Entwicklungsumgebung: csc/nmake (nothing is faster)
Herkunft: Berlin


herbivore ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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:

C#-Code:
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:

C#-Code:
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

C#-Code:
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:

C#-Code:
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.

C#-Code:
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:

C#-Code:
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:

C#-Code:
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
27.02.2005 16:30 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
DarkShadow81 DarkShadow81 ist männlich
myCSharp.de-Mitglied

Dabei seit: 22.10.2004
Beiträge: 222
Entwicklungsumgebung: VS 03,05,mcs,gmcs
Herkunft: Berlin

Themenstarter Thema begonnen von DarkShadow81

DarkShadow81 ist offline

re

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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
27.02.2005 17:56 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
VizOne VizOne ist männlich
myCSharp.de-Mitglied

avatar-1563.gif


Dabei seit: 26.05.2004
Beiträge: 1.373
Entwicklungsumgebung: VS 2010


VizOne ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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

MfG VizOne
27.02.2005 18:29 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Zwischen diesen beiden Beiträgen liegt mehr als ein Jahr.
Robert G Robert G ist männlich
myCSharp.de-Mitglied

avatar-1907.png


Dabei seit: 12.04.2006
Beiträge: 347
Entwicklungsumgebung: VS05 (Chrome/C#);TurboDel phi
Herkunft: München


Robert G ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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:

C#-Code:
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. großes Grinsen
Ein wenig relativieren muss man also schon. Augenzwinkern

Vielleicht reicht das als kleine Anregung für den FAQ Artikel....
17.04.2006 21:25 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
herbivore
myCSharp.de-Poweruser/ Experte

avatar-2627.gif


Dabei seit: 11.01.2005
Beiträge: 49.473
Entwicklungsumgebung: csc/nmake (nothing is faster)
Herkunft: Berlin


herbivore ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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
17.04.2006 21:39 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Robert G Robert G ist männlich
myCSharp.de-Mitglied

avatar-1907.png


Dabei seit: 12.04.2006
Beiträge: 347
Entwicklungsumgebung: VS05 (Chrome/C#);TurboDel phi
Herkunft: München


Robert G ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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. Augenzwinkern
17.04.2006 21:57 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
herbivore
myCSharp.de-Poweruser/ Experte

avatar-2627.gif


Dabei seit: 11.01.2005
Beiträge: 49.473
Entwicklungsumgebung: csc/nmake (nothing is faster)
Herkunft: Berlin


herbivore ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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
17.04.2006 22:09 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
VizOne VizOne ist männlich
myCSharp.de-Mitglied

avatar-1563.gif


Dabei seit: 26.05.2004
Beiträge: 1.373
Entwicklungsumgebung: VS 2010


VizOne ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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
17.04.2006 23:21 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Baumstruktur | Brettstruktur       | Top 
myCSharp.de | Forum Der Startbeitrag ist älter als 15 Jahre.
Der letzte Beitrag ist älter als 13 Jahre.
Antwort erstellen


© Copyright 2003-2020 myCSharp.de-Team | Impressum | Datenschutz | Alle Rechte vorbehalten. | Dieses Portal verwendet zum korrekten Betrieb Cookies. 29.03.2020 04:45