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

Geben Sie den Zustand einer Hashtabelle der Länge 13 an, wenn die Schlüssel

$⟨ 5, 1, 19, 23, 14, 17, 32, 30, 2 ⟩$

in die anfangs leere Datenstruktur eingefügt wurden, und ein offenes Hashverfahren mit der Hashfunktion $h (k) = k m o d 13$ sowie

(a) linearem Sondieren (Schrittweite 2)

(b) quadratischem Sondieren ( $c_{1}$ = 2, $c_{2}$ = 4)

(c) Double Hashing $(h^{'} (k) = 1 + (k m o d 5))$

verwendet wurde.

Vergleichen Sie die Anzahl der beim Einfügen betrachteten Hashtabellenplätze für die angegebenen Sondierungsfunktionen.

Lösung

$\begin{matrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ / & 1 & 2 & 14 & 17 & 5 & 19 & / & 32 & / & 23 & / & 30 \end{matrix}$

5 in 5 eingefügt
1 in 1 eingefügt
19 in 6 eingefügt
23 in 10 eingefügt
14 in 1 -> schon belegt -> lineare Sondierung -> in 3 eingefügt
17 in 4 eingefügt
32 in 6 eingefügt -> schon belegt -> lineare Sondierung -> in 8 eingefügt
30 in 4 -> schon belegt -> lineare Sondierung -> in 6 -> schon belegt -> lineare Sondierung -> in 8 -> schon belegt - > lineare Sondierung -> in 10 -> schon belegt -> lineare Sondierung -> in 12 eingefügt
2 in 2 eingefügt

$\begin{matrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ / & 1 & 2 & / & 17 & 5 & 19 & 14 & / & / & 23 & 30 & 32 \end{matrix}$

5 in 5 eingefügt
1 in 1 eingefügt
19 in 6 eingefügt
23 in 10 eingefügt
14 in 1 -> schon belegt -> quad. Sondierung -> in 7 eingefügt
17 in 4 eingefügt
32 in 6 -> schon belegt -> quad. Sondierung -> in 12 eingefügt
30 in 4 -> schon belegt -> quad. Sondierung -> in 10 -> schon belegt -> quad. Sondierung -> in 11 eingefügt
2 in 2 eingefügt

$\begin{matrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ / & 1 & 2 & / & 17 & 5 & 19 & 30 & / & 32 & 23 & 14 \end{matrix}$

5 in 5 eingefügt
1 in 1 eingefügt
19 in 6 eingefügt
23 in 10 eingefügt
14 in 1 -> schon belegt -> Double Hashing -> in 6 -> schon belegt -> Double Hashing -> in 11 eingefügt
17 in 4
32 in 6 -> schon belegt -> Double Hashing -> in 9 eingefügt
30 in 4 -> schon belegt -> Double Hashing -> in 5 -> schon belegt -> Double Hashing -> in 6 -> schon belegt -> Double Hashing -> in 7 eingefügt
2 in 2 eingefügt