|
Operatoren beim Suchen:
-MINMAXbr /
-MERGE (verschmelzen)
Beim Hashing gibt es nicht eine große, sondern viele kleine Suchstrukturen. Ein Beispiel wäre 26 (26 Buchstaben im Alphabet) Schülertabellen anzulegen.
Allgemein: Bevor man eine Strukur entwickelt entschließt man sich für eine der folgenden Operationsgruppen:
nur Hinzufügen & Löschen
oder MINMAX & Löschen
andere Ansätze:
h1 erster Buchstabe
h2 letzter Buchstabe
h3 länge des Namens
Ziel des Hashings ist es, gleichmäßige Hashfunktionen zu finden.
Einzelstruktur = Bucket (engl. Kübel)
Hashfunktion h(Pk... Primary key)
Mittels eines Algorithmuses wird bestimmt, wo das Objekt eingeordnet wird. Der Algorithmus muß so aufgebaut sein, das die Verteilung gleichmäßig erfolgt. Der ASCII- Zeichensatz ist dabei ein erster Ansatz. Das Wort besteht aus den drei unterschiedlichen Zeichencodes 200, 170 und 150. Man summiert die drei Codes, dividiert durch die Anzahl der Buchstaben im Alphabet (26!) und erhält einen Rest (modulo).
Das Verfahren ist aber nur dann optimal, wenn es mit 10 Datensätzen pro Bucket gefahren wird. Die Suche innerhalb des Buckets ist ein Array oder einfach eine verkettet Liste (Separate Chaining).
Linear Probing
Bei der Methode des Linear Probing verwenden wir pro Bucket einen Datensatz.
Was geschieht aber, wenn durch das Linear Probing ein Österreicher in ein Feld geschoben werden mußm daß schon besetzt ist? Die Lösung sind verschiedene Schrittweiten z.B. 2 Funktionen, auch genannt Double Hashing (gleichmäßigere Vererbung). Die Vorraussetzung für dieses Verfahren ist, daß es mehr Buckets als Datensätze geben muß.
Indirektes Suchen (Indirect Search)
(vgl. Buchindex am Ende eines Buches = Sortierte Datenstruktur mit einem Pointer auf Seiten)
INDEX= Für jedes Suchkriterium ein eigener Hilfsbaum (für schnelle Rückantwort)
für langsame Rückantwort sequentiell
Statt dem Baum kann man auch eine geordnete Liste erstellen.
|
