30 Hastabelle
30.1 Was ist Hashing?

Einige Ideen stammen aus dem Buch:

 

Helmut Balzert - Lehrbuch Grundagen der Informatik
Gebundene Ausgabe - Spektrum Akademischer Verlag
Erscheinungsdatum: September 2004
ISBN: 3827403588

 

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:
 

Index
Wort
Schlüssel
Übersetzung
Schlüsselwert
0    
1    
2 Warteschlange queue
3    
4    
5    
6    
7 Keller stack
8    

 

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