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

Wir betrachten offene Hashverfahren mit einer Hashtabelle T der Größe $m=13$. Nach dem Einfügen der Elemente $\left\langle 21,27,22,20,37,12\right\rangle$ präsentiert sich der Zustand der Hashtabelle wie folgt:

${\begin{array}{c||c|c|c|c|c|c|c|c|c|c|c|c|c}{\text{Index}}&0&1&2&3&4&5&6&7&8&9&10&11&12\\\hline {\text{Schlüssel}}&13&27&2&&&&6&20&21&22&10&37&12\\\hline {\text{Status}}&W&B&W&F&F&F&W&B&B&B&B&B&B\\\end{array}}$

Die Buchstaben F, B und W stehen jeweils für Frei, Besetzt und Wieder frei. Als nächstes soll das Element 9 eingefügt werden.

(a) Benutzen Sie lineares Sondieren und die Hashfunktion $h'(k)=k~mod~13$ Welche Position werden in diesem Fall beim Einfügen von 9 überprüft?

(b) Benutzen Sie quadratisches Sondieren und die Hashfunktion $h'(k)=k~mod~13$ sowie die Konstanten $c_{1}=4$ und $c_{2}=2$. Welche Positionen werden nun beim Einfügen von 9 überprüft?

Löschen Sie nun 12 aus der Hashtabelle und fügen Sie anschließen 34 mittels quadratischem Sondieren (mit den oben genannten Konstanten) ein.

Lösung

Einfügen mit linearem Sondieren

9 mod 13 = in 9 -> schon besetzt -> in 10 -> schon besetzt -> in 11 -> schon besetzt -> in 12 -> schon besetzt -> in 0 -> 0 ist wieder frei, 9 in 0 eingefügt, T[0].Status = B

Einfügen mit quad. Sondieren

9 mod 13 = in 9 -> schon besetzt -> quad. Sondieren -> 2 wiederfrei, 9 in 2 eingefügt, T[2].Status = B

12 löschen

T[12].Status = W

${\begin{array}{c||c|c|c|c|c|c|c|c|c|c|c|c|c}{\text{Index}}&0&1&2&3&4&5&6&7&8&9&10&11&12\\\hline {\text{Schlüssel}}&13&27&2&&&&6&20&21&22&10&37&12\\\hline {\text{Status}}&W&B&W&F&F&F&W&B&B&B&B&B&W\\\end{array}}$

34 einfügen

34 mod 13 = in 8 -> schon besetzt -> quad. Sondieren -> in 1 -> schon besetzt -> quad. Sondieren -> in 11 -> schon besetzt -> quad. Sondieren -> in 12, 12 wieder frei, 34 in 12 eingefügt, T[12].Status = B

${\begin{array}{c||c|c|c|c|c|c|c|c|c|c|c|c|c}{\text{Index}}&0&1&2&3&4&5&6&7&8&9&10&11&12\\\hline {\text{Schlüssel}}&13&27&2&&&&6&20&21&22&10&37&34\\\hline {\text{Status}}&W&B&W&F&F&F&W&B&B&B&B&B&B\\\end{array}}$