30 Hastabelle 30.1 Was ist Hashing? Einige Ideen stammen aus dem Buch:
Helmut Balzert -
Lehrbuch Grundagen der Informatik |
|||||||||||||||||||||||||||||||
Suchen durch Vergleich | Suchen
ist ein in informatischen Systemen häufiger Vorgang. Deshalb ist man an
effizienten Suchalgorithmen interessiert. Oft entscheidet ein Datentyp
darüber, welches Suchverfahren man anwendet. Sind Daten in einer Liste, in
einem Keller oder in einem Baum abgelegt, so werden für diese Datentypen
spezifische Suchverfahren verwendet. Ohne dass wir uns diesen spezifischen
Algorithmen zuwenden wollen, kann man sich doch leicht vorstellen, dass
alle eines gemeinsam haben: das Vergleichen eines aktuellen Eintrags in
der Liste bzw. Keller oder Baum mit dem Suchbegriff. Wir können also
sagen, dass alle diese Verfahren
vergleichs-orientiert sind. (Vergleichen Sie dazu Aufgabe 1 in
30.5 Übungen) |
||||||||||||||||||||||||||||||
schlüsselindi-ziertes Suchen | Anders
kann man Suchen gestalten, wenn die Daten in einem Array oder Feld
gespeichert sind. Die einzelnen Plätze werden über Indizes (= Platznummer)
angesprochen. Stehen Index eines Platzes und der Inhalt des Platzes in
einem inhaltlichen oder sonst einem organisierten Zusammenhang, so
kann man das Suchen in einem solchen Feld durch einen Zugriff über den
Index sehr schnell und effizient realisieren. Wir vergleichen also nicht
mehr die Schlüsselwerte, sondern wir verwenden den Schlüssel für einen
direkten Zugriff auf den Schlüsselwert. (Vergleichen Sie dazu Aufgabe 2 in
30.5 Übungen) |
||||||||||||||||||||||||||||||
Hashing = Streuspeicherung | Hashing
ist ein Verfahren, das dem Suchen in einem indizierten Feld gleicht.
Machen wir uns dieses Verfahren an einem konkreten Beispiel klar. Wir
wollen ein Übersetzungslexikon erstellen. Jedem deutschen Wort soll seine
englische Übersetzung zugeordnet werden. Etwa: Keller -> stack oder Feld
-> array. Die Daten legen wir in einer Tabelle ab:
Suchen durch Vergleich würde
bedeuten, dass man die ganze Tabelle durchsucht, dabei den Schlüssel mit
dem Suchschlüssel vergleicht, bis man Übereinstimmung findet (Ziel
erreicht) oder ans Ende der Tabelle ankommt (Mißerfolg). Im Erfolgsfall
hat man den gewünschten Schlüsselwert, in unserem Fall also die englische
Übersetzung des Suchschlüssels. Ein indexorientiertes Suchen geht gänzlich
anders. Wenn man weiß, dass zum Suchbegriff Keller der Index 7 gehört,
dann brauchen wir nur noch in der Zeile 7 nachschauen. Wie kann man aber
feststellen, dass zu 'Keller' der Index 7 gehört. Hier spielt der Begriff
der Hashfunktion eine große Rolle. |
||||||||||||||||||||||||||||||
zu | 30.2 Hashfunktion | ||||||||||||||||||||||||||||||
zur Startseite | www.pohlig.de (C) MPohlig 2004 |