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

$\left\langle 5,1,19,23,14,17,32,30,2\right\rangle$

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

(a) linearem Sondieren (Schrittweite 2)

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

(c) Double Hashing $(h'(k)=1+(k~mod~5))$

verwendet wurde.

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

Lösung

Teil (a)

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

• 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

Teil (b)

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

• 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

Teil (c)

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

• 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