Hashing < Sonstiges < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:27 Do 26.06.2008 | | Autor: | barsch |
| Aufgabe | Gebe die Belegung einer Hash-Tabelle der Länge 13 an, wie die Schlüssel
14, 1, 32, 19
in der angegebenen Reihenfolge eingefügt werden und geschlossenes Hashing mit der Hash-Funktion [mm] h(k)=k\text{ mod }13 [/mm] mit Sondierungsfolge double Hashing mit [mm] h_2(k)=1+k\text{ mod }11. [/mm] |
Hi,
habe hier ein kleines Problem.
Ich fange einmal an:
h(14)=14 mod 13 = 1 [mm] \green{okay}
[/mm]
h(1)=1 mod 13 = 1 [mm] \green{\text{soweit ist das auch noch in Ordnung. Jetzt kommt }h_2\text{ ins Spiel:}}
[/mm]
Nach VL muss ich so vorgehen:
[mm] h(1)-h_2(1)=1-(1+1 [/mm] mod 11)=-1 [mm] \red{\text{Was jetzt? -1 exisitiert ja nicht.}}
[/mm]
Die Hashtabelle sieht ja so aus:
0 1 2 3 4 5 6 7 8 9 10 11 12
14
Selbes im nächsten Schritt:
h(32)=32 mod 13=6 Okay.
h(19)=19 mod 13=6
Es folgt Vorgang von eben:
[mm] h(19)-h_2(19)=6-(1+ [/mm] 19 mod 11)=6-(1+8)=-3
Aber auch hier: -3 ist ja nicht in der Tabelle. Wie also sind 1 und 19 einzuordnen?
HashTabelle bis jetzt:
0 1 2 3 4 5 6 7 8 9 10 11 12
14 32
Vielen Dank.
MfG barsch
Ich habe diese Frage in keinem anderen Forum gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:48 Do 26.06.2008 | | Autor: | ardik |
Hallo barsch,
mit dem Thema bin ich nicht vertraut, aber das:
> Nach VL muss ich so vorgehen:
>
> [mm]h(1)-h_2(1)=1-(1+1[/mm] mod 11)=-1 [mm]
ist mir hochgradig suspekt.
Meines Erachtens muss grundsätzlich etwas in der Form
(...) mod 11
verwendet werden, wobei in der Klammer irgendeine Kombination der Hash-Funktion und der alternativen Hash-Funktion stehen müsste. Nur so werden ja geeignete Ergebnisse sichergestellt.
Dies wird auch durch meine Google- (und Wikipedia-) Schnellrecherche gestützt.
Viel Erfolg!
Schöne Grüße
ardik
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:16 Do 26.06.2008 | | Autor: | barsch |
Hi,
danke für die Antwort.
> Hallo barsch,
>
> mit dem Thema bin ich nicht vertraut, aber das:
>
> > Nach VL muss ich so vorgehen:
> >
> > [mm]h(1)-h_2(1)=1-(1+1[/mm] mod 11)=-1 [mm]
> ist mir hochgradig suspekt.
Aber genau so muss ich vorgehen. So steht's bei mir im Skript. 
Die HashTabelle sieht am Ende so aus:
0 1 2 3 4 5 6 7 8 9 10 11 12
14 32 19 1
Habe ich erst vorenthalten (sorry). Weil mir der Weg nicht klar war.
Ich glaube, ich habe jetzt eine Idee. Bevor ich die aber poste, will ich
mir erst noch mal Gedanken darüber machen, ob das so sein könnte,
wie ich denke.
MfG barsch
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:52 Do 26.06.2008 | | Autor: | rainerS |
Hallo!
> Gebe die Belegung einer Hash-Tabelle der Länge 13 an, wie
> die Schlüssel
>
> 14, 1, 32, 19
>
> in der angegebenen Reihenfolge eingefügt werden und
> geschlossenes Hashing mit der Hash-Funktion [mm]h(k)=k\text{ mod }13[/mm]
> mit Sondierungsfolge double Hashing mit [mm]h_2(k)=1+k\text{ mod }11.[/mm]
>
> Hi,
>
> habe hier ein kleines Problem.
>
> Ich fange einmal an:
>
> h(14)=14 mod 13 = 1 [mm]\green{okay}[/mm]
>
> h(1)=1 mod 13 = 1 [mm]\green{\text{soweit ist das auch noch in Ordnung. Jetzt kommt }h_2\text{ ins Spiel:}}[/mm]
>
> Nach VL muss ich so vorgehen:
>
> [mm]h(1)-h_2(1)=1-(1+1[/mm] mod 11)=-1 [mm]\red{\text{Was jetzt? -1 exisitiert ja nicht.}}[/mm]
Du musst Alles mod 11 rechnen, was nichts Anderes heisst, als dass du ein passendes Vielfaches von 11 dazuaddieren musst:
[mm] -1 \equiv 10 \pmod{11} [/mm]
Kongruenz [mm] $\pmod{11}$ [/mm] bedeutet ja nur, dass die Differenz der Zahlen ein Vielfaches von 11 ist.
Viele Grüße
Rainer
|
|
|
|
