This flashcard is just one of a free flashcard set. See all flashcards!
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:
Source: Kapitel 7
Source: Kapitel 7
Flashcard info:
Author: kread
Main topic: Informatik
Topic: Datenbanken
School / Univ.: Universität Koblenz-Landau
City: Koblenz
Published: 18.10.2010