TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 25

Aus VoWi
Zur Navigation springen Zur Suche springen

Gegeben ist eine Hashtabelle mit Tabellengröße m = 7, die Double Hashing mit der Verbesserung nach Brent benutzt:

= k mod 7

= 3k mod 5+2

Die Werte wurden bereits in die Tabelle eingefügt:

Fügen Sie zuerst die Werte in dieser Reihenfolge ein. Dann löschen Sie 13 und fügen 15 ein.

Lösung[Bearbeiten | Quelltext bearbeiten]

Einfügen von 8[Bearbeiten | Quelltext bearbeiten]

h(8,0) = 1, Kollision mit 1 h(8,1) = = 7 mod 7 = 0 -> in 0 einfügen

Einfügen von 17[Bearbeiten | Quelltext bearbeiten]

h(17,0) = 3 -> Kollision h(17,1) = = 6 -> Kollision mit 13 VnB = (3,1) = = 2 -> 3 in 2 eingefügt, 17 in 3 eingefügt

Tabelle nach dem Einfügen[Bearbeiten | Quelltext bearbeiten]

Löschen von 13[Bearbeiten | Quelltext bearbeiten]

Einfügen von 15[Bearbeiten | Quelltext bearbeiten]

h(15,0) = 1 -> Kollision mit 1 h(15,1) = = 3 -> Kollision mit 17 VnB = (1,1) = = 6 -> 1 in 6 eingefügt, 15 in 1 eingefügt

Tabelle am Ende[Bearbeiten | Quelltext bearbeiten]