Quadratisches Sondieren (Hash) < Datenstrukturen < Schule < Informatik < Vorhilfe
|
| Aufgabe | Fügen Sie die Schlüsselfolge 9, 26, 12, 18, 33, 15, 22 gemäß der Hashfunktion
h(x) = [mm] h_0(x) [/mm] = x mod 7 in eine anfangs leere Hashtabelle (Feld mit Feldindex von 0 bis 6) ein.
Lösen Sie Kollisionen durch quadratisches Sondieren mit wechselndem Vorzeichen, wobei gilt:
[mm] h_i(x) [/mm] = (h(x) + [mm] i^2) [/mm] mod 7 für i = 1, 3, 5, ...
[mm] h_i(x) [/mm] = (h(x) - [mm] i^2) [/mm] mod 7 für i = 2, 4, 6, ...
Indexposition 0 1 2 3 4 5 6
Wert _ _ _ _ _ _ _ |
Wenn man mit dem ersten Wert (9) anfängt, gab es ja noch keine Kollisionen, dementsprechend ist i = 0.
Für die ersten beiden Werte kommt man ohne Kollisionen ans Ziel.
9 -> Index 2
26 -> Index 5
bei der 12 bekommt man zunächst den Index 5, was eine Kollision bedeutet, da dort bereits der Wert 26 liegt.
Ich setze also den Wert i auf 1 und wende an:
[mm] h_1(12) [/mm] = (5 + 1) mod 7 = 6
Muss ich mir diese Kollision merken bzw. bleibt i jetzt auf 1?
Zum Beispiel beim Wert 33 komme ich mit h(33) bzw. [mm] h_0(33) [/mm] auf den Index 5, also Kollision (insgesamt die 2. Kollision). Berechne ich hier zunächst [mm] h_1(33) [/mm] dann [mm] h_2(33) [/mm] dann [mm] h_3(33) [/mm] usw. bis ich auf einen freien Index stoße oder kann ich nach der [mm] h_0(33)-Kollision [/mm] direkt bei [mm] h_2(33) [/mm] weiterprüfen und damit [mm] h_1(33) [/mm] überspringen, da ich mit meinem i auf zwei bin.
Aus Programmierer-Sicht: Ist dieses i eine globale Variable oder eine lokale Variable.
Danke
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:20 Do 11.08.2016 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
