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

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

$h_{\text{1}}(k)$ = k mod 7

$h_{\text{2}}(k)$ = 3k mod 5+2

Die Werte $⟨1,3,13⟩$ wurden bereits in die Tabelle eingefügt:

$\begin{array}{ccccccc}0& 1& 2& 3& 4& 5& 6\\ \text{HLINE TBD}& 1& & 3& & & 13\end{array}$

Fügen Sie zuerst die Werte $⟨8,17⟩$ in dieser Reihenfolge ein. Dann löschen Sie 13 und fügen 15 ein.

Lösung

Einfügen von 8

h(8,0) = 1, Kollision mit 1 h(8,1) = $(1+(24mod5+2))mod7$ = 7 mod 7 = 0 -> in 0 einfügen

Einfügen von 17

h(17,0) = 3 -> Kollision h(17,1) = $(3+(51mod5+2))mod7$ = 6 -> Kollision mit 13 VnB = (3,1) = $(3+(21mod5+2))mod7$ = 2 -> 3 in 2 eingefügt, 17 in 3 eingefügt

Tabelle nach dem Einfügen

$\begin{array}{ccccccc}0& 1& 2& 3& 4& 5& 6\\ \text{HLINE TBD}8& 1& 3& 17& & & 13\end{array}$

Löschen von 13

$\begin{array}{ccccccc}0& 1& 2& 3& 4& 5& 6\\ \text{HLINE TBD}8& 1& 3& 17& & & \end{array}$

Einfügen von 15

h(15,0) = 1 -> Kollision mit 1 h(15,1) = $(1+(45mod5)+2)mod7$ = 3 -> Kollision mit 17 VnB = (1,1) = $(1+(3mod5)+2)mod7$ = 6 -> 1 in 6 eingefügt, 15 in 1 eingefügt

Tabelle am Ende

$\begin{array}{ccccccc}0& 1& 2& 3& 4& 5& 6\\ \text{HLINE TBD}8& 15& 3& 17& & & 1\end{array}$