Kurs:Algorithmen und Datenstrukturen/Vorlesung/Hashtabellen dynamischeHashverfahren

Dynamische Hashverfahren

Auf dieser Seite werden die dynamischen Hashverfahren behandelt.

Das Problem statischer Hashverfahren ist, dass es einen festen Bildbereich gibt und dadurch zusätzliche mehr Einträge einen Neuaufbau einer größeren Hashtabelle erfordern. Die Lösung des Problems sind die dynamischen Hashverfahren mit dynamisch wachsenden oder schrumpfenden Bildbereichen. Die wachsenden Bildbereiche werden etwa durch Verdopplung erreicht. Die Funktionsfamilie, definiert auf dem Bereich der zu speichernden Elemente E lautet

$h_i:E\to o,...,2^{i}N-1$

Hier haben wir eine Folge von Hashfunktionen mit $i\in 0,1,2,...$. N ist die Anfangsgröße des Hashverzeichnisses. Der Wert von i ist das Level der Hashfunktion.

Lokales Wachstum

Das Ziel ist das vermeiden von Rehashen bei der Verdopplung eines Bildbereichs, d.h :

• $h_{(}i+1)(w)=h-i(w)$ für etwa die Hälfte aller $w\in E$
• $h_{(}i+1)(w)=h_i(w)+2^{i}N$ für die andere Hälfte.

Elemente die einem Bucket j durch $h_i$ zugeordnet werden, werden durch $h_{(}i+1)$ also auf jeweils eines von zwei Buckets verteilt: j oder $j+(2^{i}N)$. Damit ist das Ziel erfüllt durch $h_i(w)=wmod(2^{i}N)$.

Bitvektordarstellung

Statt Familien von Hashfunktionen wird hier genau eine Funktion zugeordnet. Das Zielbereich ist das Intervall [0.0...1.0] hier werden keine ganzen Zahlen verwendet, sondern Gleitpunktzahlen. Es ist eine gleichmäßige Verteilung auf den Zielbereich gefordert.

Die Hashwerte im binären Zahlensystem sehen wie folgt aus:

0.0= b0.000000...

0.5= b0.100000...

0.75 = b0.110000...

0.99999... = b0.111111...

Die ersten i Bits hinter dem Punkt adressieren ein Feld der Größe $2^i$. Die Hinzunahme eines Bits verdoppelt nun den Bildbereich.