Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!
23
Hashing
Bei Bäumen hat man immer noch log(n) Seitenzugriffe, einen pro Kantenverfolgung. Beim Hashing wird eine fast eindeutige Zuordnung von Schlüssel zu Bucket erreicht.
Statisches Hashing:
Erweiterbares Hashing:
Statisches Hashing:
- A priori Speicher alloziieren, nachträgliche Vergrößerung ist durch Rehashing teuer.
- Hashfunktion meist mod Anzahl Buckets.
Erweiterbares Hashing:
- Präfix des Hashwertes der Länge n zur Bestimmung des Buckets verwendet.
- Anfangs kleiner Präfix, kann wachsen.
- Zwischen globaler Tiefe (n) und lokaler Tiefe (Anzahl Bits, die in diesem Bucket wirklich verwendet werden) unterscheiden
- Bei Overflow globale Tiefe und ggf. lokale Tiefe erhöhen
- Bei Löschen falls lokale Tiefe überall < globale Tiefe, globale Tiefe senken
Tags:
Quelle: Kapitel 7
Quelle: Kapitel 7
Karteninfo:
Autor: kread
Oberthema: Informatik
Thema: Datenbanken
Schule / Uni: Universität Koblenz-Landau
Ort: Koblenz
Veröffentlicht: 18.10.2010