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

Eine Hashtabelle soll bis zu 7500 Einträgen aufnehmen. Die Schlüssel sind Zahlen im Bereich [0, 10000]. Der Hashwert wird mit der Divisions-Rest-Methode ermittelt, und die Kollisionsbehandlung erfolgt mittels Double Hashing.

(a) Geben sie für jede der folgenden Zahlen an, ob sie eine gute Wahl für die Tabellengröße m wäre und begründen Sie Ihre Entscheidung:

8192, 7499, 35537, 7507, 8999

(b) Bestimmen Sie für eine geeignete Wahl der Tabellengröße aus (a) entsprechende Funktionen $h_{\text{1}}(k)$ und $h_{\text{2}}(k)$.

(c) Warum ist die folgende Funktion eine schlecht Wahl $h_{\text{2}}(k)$?

$h_{\text{2}}(k)={\begin{cases}m-h_{\text{1}}(k),\,falls\,h_{\text{1}}(k)\neq 0\\1\,sonst\end{cases}}$

Wie kann das Problem der Hashfunktion behoben werden?

Frage (a)

7499: ist kleiner als m, deswegen zu wenig Platz -> ungeeignet

7507: nur ein bisschen größer als m, hohe Anzahl von Kollisionen -> ungeeignet

8192: von der Größe her möglich, jedoch eine 2er-Potenz -> ungeeignet

35537: Zu groß, jedoch Primzahl -> aufgrund der Größe ungeeignet

8999: Zahl ~20% größer als m, Primzahl -> geeignet

Frage (b)

$h_{\text{1}}(k)$ = k mod 8999

$h_{\text{2}}(k)$ = 1 + (k mod 8997)

Frage (c)

Die Funktionen sind eine schlechte Wahl da die Funktionen von einander anhängig sein müssen. laut Tutor: durch erster Sondierungsschritt auf 0 , => ungünstig

Beweis:

h(4,1) = $h_{\text{1}}(k)$ + 1 * $h_{\text{2}}(k)$ = $h_{\text{1}}(k)$ + m - $h_{\text{1}}(k)$ = m => m mod m = 0 -> ineffizient