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 $⟨21,27,22,20,37,12⟩$ präsentiert sich der Zustand der Hashtabelle wie folgt:

$\begin{array}{cccccccccccccc}\text{Index}& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12\\ \text{Schlüssel}& 13& 27& 2& & & & 6& 20& 21& 22& 10& 37& 12\\ \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^{\prime }(k)=kmod13$ Welche Position werden in diesem Fall beim Einfügen von 9 überprüft?

(b) Benutzen Sie quadratisches Sondieren und die Hashfunktion $h^{\prime }(k)=kmod13$ 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}{cccccccccccccc}\text{Index}& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12\\ \text{Schlüssel}& 13& 27& 2& & & & 6& 20& 21& 22& 10& 37& 12\\ \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}{cccccccccccccc}\text{Index}& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12\\ \text{Schlüssel}& 13& 27& 2& & & & 6& 20& 21& 22& 10& 37& 34\\ \text{Status}& W& B& W& F& F& F& W& B& B& B& B& B& B\end{array}$