www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Datenstrukturen" - Quadratisches Sondieren (Hash)
Quadratisches Sondieren (Hash) < Datenstrukturen < Schule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Quadratisches Sondieren (Hash): Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 00:42 Fr 05.08.2016
Autor: shaquanda

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.

        
Bezug
Quadratisches Sondieren (Hash): Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 01:20 Do 11.08.2016
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]