Bsp. Double Hashing

[sheybe]

hi!

kann mir wer bitte genau erklären, wie das Bsp. für Double Hashing im Skriptum( auf S. 109 oben) funktioniert? Ich verstehs eh- nur häng ich dann beim Einfügen von k = 14 ..... hmm irgendwie komm ich nicht auf Platz 6 :hewa: ... is wahrscheinlich eh voll leicht, oba ich sehs nicht.... :confused:

[Sensei]

Habs mir angeschaut... du machst wahrscheinlich den Fehler, dass du in h(k,i) hinten 5 als Modulowert einsetzt, und nicht 7 (was dorthin gehört, weil wir m nehmen)... wenn man 7 einsetzt:
h(k,i) = ( h1(k) + h2(k)*i ) mod m
h(14,0) = ( 0 + 5*0 ) mod 7 = 0 (besetzt)
h(14,1) = ( 0 + 5*1 ) mod 7 = 5 (besetzt)
h(14,2) = ( 0 + 5*2 ) mod 7 = 3 (besetzt)
h(14,3) = ( 0 + 5*3 ) mod 7 = 1 (besetzt)
h(14,4) = ( 0 + 5*4 ) mod 7 = 6 (FREI)

Du bist also auf Platz 6 gelandet - zugegebenermaßen nach langwierigen Berechnungen ;)

ciao, hoffe alles is klar

[sheybe]

aha ja sicher- jetz seh ichs auch
ma danke, he :thumb:

[Tiniiiii]

Irgendwie konnte ich noch kein Posting mit einer Lösung zum 2. Beispiel von Test C vom SS 02 finden (zwecks Vergleich). & nachdem mitlerweile schon fast 100.000 AlgoDat-Übungs-Threads existieren häng' ich mal hier meine Lösung an und hoffe, dass Euch das selbe rauskommt ....

Angabe: Skizzieren Sie eine Hashtabelle mit m=11 Feldern und tragen Sie mittels Double Hashing folgende Werte in der gegebenen Reihenfolge ein: <14 , 7 , 10 , 3 , 12 , 11 , 18>

Die Hashfunktionen lauten: h1(k) = (5 + 2k) mod m h2(k) = 3 + (k mod 5)

Formel f. Double Hashing (nicht in Angabe): h(k,i) = (h1(k) + ih2(k)) mod m

k: 14 7 10 3 12 11 18
-----------------------------------
h(k,0): 0 8 3 0 7 5 8
h(k,1): 6 3
h(k,2): 9

Hashtabelle:
0 1 2 3 4 5 6 7 8 9 10
---------------------------------
14 10 11 3 12 7 18


lg Martina

Edit: Hm ... hab mich wohl verrechnet. :shout:
Hasse diese Schlampigkeitsfehler. Ich hoffe nur mir passiert morgen so was nicht!!! Jetzt ists ausgebessert ...

[sheybe]

hmmm??:confused: ich komm auf:

0 -> 14
1
2
3 -> 10
4 -> 11
5 -> 12
6 -> 3
7
8 -> 7
9 -> 18
10

aber wers nochmal durchgehn..... :confused:

[Tiniiiii]

@sheybe: Dein Posting ist bissi unübersichtlich - Du solltest das Ganze als Code eingeben - dann sollten die Abstände passen ...

oh - hat sich erübrigt ...

[sheybe]

ma entschuldigung entschuldigung!!! erstens mal für absolut furchtbares formatieren
und zweitens für falsche Lösung!!!! :ahhh:

@ Tiniiiiiii deins stimmt schon- bins noch einmal durch- und komm jetz gottseidank auch aufs Gleiche

[lEn00x]

Also ich komme auch auf diese Lösung hier:
0:14
1:
2:
3:10
4:
5:11
6:3
7:12
8:7
9:18
10:

[Mr. Zet]

falls die angabe von Tinii nicht von der vom Test abweicht (hab ned nachgeschaut), dann kommt folgendes heraus:

h(k)|k
-------
0| 14
1|
2|
3| 10
4|
5| 11
6| 3
7| 12
8| 7
9| 18
10|


edit: same as len00x
aber wieso schreibst du "auch" wenn vor dir noch keiner diese lösung hatte? ;)

[Tiniiiii]

Und weils grad soooooo lustig war hab ich auch gleich Aufgabe 2A vom 2. Übungstest SS 02 auch gelöst:

Angabe: Skizzieren Sie eine Hashtabelle mit m=11 Feldern und tragen Sie mittels Double Hashing folgende Werte in der gegebenen Reihenfolge ein: <7,16,2,18,6,11,13>

Die Hashfunktionen lauten: h1(k) = (32 - k) mod m h2(k) = 2+ (k mod 7)

k: 7 16 2 18 6 11 13
-----------------------------------
h(k,0): 3 5 8 3 4 10 8
h(k,1): 9 5
h(k,2): 2

Hashtabelle:
0 1 2 3 4 5 6 7 8 9 10
---------------------------------
13 7 6 16 2 18 11

[sheybe]

so noch mal durchgegangen und komm jetzt auf:

0 -> 14
1 ->
2
3 -> 10
4 ->
5 -> 11
6 -> 3
7 -> 12
8 -> 7
9 -> 18
10 ->

bei mir ist beim 3er : h(k,i) = ( 0 + 1 * 6) mod 11
oder hab ich mich da verrechnet?? :confused:


edit: zu spät!!

[Mr. Zet]

tinii, was meinst du immer mit h3(k), h4(k) usw. ? das gibt es ja gar nicht ...

du machst irgendwas falsch..
zB im ersten post bei 18

richtig wäre folgendes:
(5+ 18*2)mod 11 + 0 = 8 ->besetzt also weiter
(8 +(3 + (8 mod 5)) )mod 11 = 3 -> besetzt, weiter
(8 + (2*(3 + (8 mod 5))) mod 11 = 9 -> fertig

[sheybe]

@ Tiniiiiiii beim 2. Bsp komm ich auch aufs selbe wie du--- werd schon so passen ;)

[Tiniiiii]

tinii, was meinst du immer mit h3(k), h4(k) usw. ? das gibt es ja gar nicht ...

Naja - ich hab mich halt schon beim Einfügen vom 3er verrechnet - drum hats nicht gestimmt ... Aber jetzt passts!
Mit h3(k) etc. trage ich meine Rechenschritte für die schon besetzten Positionen ein - damits übersichtlich wird ... Nachdem ich das selbe Ergebnis hab wie die anderen wird diese Variante schon passen (hoff ich).

Ganz richtig wäre h(k,0), h(k,1) ... wobei 0,1,... in dem Fall für i steht.

lg

[lEn00x]

EDIT: hat sich schon erübrigt

[Mr. Zet]

@ tinii, ok, verstehe schon ;)