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

Aus VoWi
Zur Navigation springen Zur Suche springen

Wir betrachten offene Hashverfahren mit einer Hashtabelle T der Größe . Nach dem Einfügen der Elemente präsentiert sich der Zustand der Hashtabelle wie folgt:

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 Welche Position werden in diesem Fall beim Einfügen von 9 überprüft?

(b) Benutzen Sie quadratisches Sondieren und die Hashfunktion sowie die Konstanten und . 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[Bearbeiten | Quelltext bearbeiten]

Einfügen mit linearem Sondieren[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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

12 löschen[Bearbeiten | Quelltext bearbeiten]

T[12].Status = W

34 einfügen[Bearbeiten | Quelltext bearbeiten]

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