Kurs:Algorithmen und Datenstrukturen/Vorlesung/Hashtabellen dynamischeHashverfahren

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

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)=w~mod(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.