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 $\left\langle 1,3,13\right\rangle$ wurden bereits in die Tabelle eingefügt:

${\begin{array}{c|c|c|c|c|c|c}0&1&2&3&4&5&6\\\hline \hline &1&&3&&&13\\\end{array}}$

Fügen Sie zuerst die Werte $\left\langle 8,17\right\rangle$ 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+(24~mod~5+2))~mod~7$ = 7 mod 7 = 0 -> in 0 einfügen

Einfügen von 17

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

Tabelle nach dem Einfügen

${\begin{array}{c|c|c|c|c|c|c}0&1&2&3&4&5&6\\\hline \hline 8&1&3&17&&&13\\\end{array}}$

Löschen von 13

${\begin{array}{c|c|c|c|c|c|c}0&1&2&3&4&5&6\\\hline \hline 8&1&3&17&&&\\\end{array}}$

Einfügen von 15

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

Tabelle am Ende

${\begin{array}{c|c|c|c|c|c|c}0&1&2&3&4&5&6\\\hline \hline 8&15&3&17&&&1\\\end{array}}$