Double Hasing
Results 1 to 14 of 14

Thread: Double Hasing

  1. #1
    fraka79

    Question Double Hashing

    hy; hab folgende Angabe:

    Gegeben ist die Zahlenfolge 19,12,7,30,5,10,15,29,3,23,4 & die beiden Hasfunkionen h1 = k mod 13, h2 = k mod 7. Fügen Sie die Elemente mit Hilfe von Double Hasing in eine Hash-Tabelle mit 11 Positionen, numeriert von 0 bis 10 ein!

    Bei mir kommt folgendes raus:
    0: 23
    1: 12
    2: 15
    3: 29
    4: 30
    5: 5
    6: 19
    7: 7
    8: 4
    9: 3
    10: 10

    hat jemand das selbe, oder lieg ich total falsch???
    danke,
    lg franz

    ** special thx to laborg* hasHing

  2. #2
    RoadRash's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Oberwart / Wien
    Posts
    274
    Thanks
    0
    Thanked 0 Times in 0 Posts
    bekomme genau das gleiche ergebnis raus (und finde keinen fehler).

    dürfte passen...
    Ceterum censeo, carthaginem esse delendam.

  3. #3

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    780
    Thanks
    25
    Thanked 18 Times in 8 Posts
    nenns hasHing ...hört sich besser an....

  4. #4

    Title
    Veteran
    Join Date
    May 2002
    Posts
    12
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Kann mir bitte kurz wer erklären wie das Double Hashing funktionieren soll.
    Normalerweise ist die Sondierungsfolge ja H1, H1-H2, H1-2H2...
    oder täuscht mich das? Steht zumindest in dem einen empfohlenen AlgoDat Buch so drinnen. Aber das obige Beispiel krieg ich einfach so nicht hin. Eine kleine Erklärung wär nett. Thx

  5. #5
    fraka79
    also ich habs nach den von dir genannten Regeln gemacht:

    sprich du hast dann folgende Tabelle:
    (irgendwo soll ein attachment aufscheinen)

    das einzige wos zum rechnen wird:
    ist bei 3, 23 und 4


    so long
    franz
    Attached Images Attached Images  

  6. #6
    RoadRash's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Oberwart / Wien
    Posts
    274
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Original geschrieben von MrFloppy
    Normalerweise ist die Sondierungsfolge ja H1, H1-H2, H1-2H2...
    oder täuscht mich das?
    Laut AlgoDat-Skriptum, ist
    h(k,i) = h1(k)+i*h2(k)

    sprich:
    h1(k)
    h1(k)+h2(k)
    h1(k)+2*h2(k)
    and so on...

    ich habs so gerechnet und es ist das obige ergebnis herausgekommen...
    Ceterum censeo, carthaginem esse delendam.

  7. #7

    Title
    Veteran
    Join Date
    May 2002
    Posts
    12
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Danke

    Jeztt hab ichs auch geschnallt.
    Hab vergessen bei (h1 + i*h2) mod m zu nehmen !

    jetzt gehts sich auch aus.

    thx to all

  8. #8
    RoadRash's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Oberwart / Wien
    Posts
    274
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ja, sorry das mod m hab ich vergessen, aber das ergibt sich eh automatisch, wenn mal werte > 1000 für ein n=11 herauskommen
    Ceterum censeo, carthaginem esse delendam.

  9. #9

    Title
    Veteran
    Join Date
    May 2002
    Posts
    12
    Thanks
    0
    Thanked 0 Times in 0 Posts

    kurze Frage noch

    Angenommen ich sollte die Zahl "30" in eine Hashtabelle mit 0 - 10 eintragen und fie Funktionen lauten:

    h1 = k mod 17
    h2 = (K mod 5)+1

    bekomme ich ja bei 30 mod 17 -> 13 heraus. nehm ich die Zahl dann sofort mod m? Wenn nicht, wie funktionierts dann?

  10. #10
    fraka79
    kann dir zu leider nicht helfen

    könnt mir aber kurz wer in dt. sätzen erklären
    wie die methode nach brent funktioniert?????
    kann da einiges nicht nachvollziehen.
    danke

  11. #11
    fraka79
    zu mrfloppy post #9:

    ok ich glaub du nimmst hier bezug auf die prüfung vom 28.01.2002:

    ich hab's bei der 30 so gemacht:
    30 mod 17 -> 13 mod 11 -> 2 und da die schon besetzt ist (in diesem fall von 19) geb ich h2(k) in diesem fall 1 dazu und somit wird die 30 auf 3 gespeichert.

    hoff das stimmt
    so long
    franz

  12. #12
    eXe's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    99
    Thanks
    0
    Thanked 0 Times in 0 Posts
    is zwar eigtl schon geklärt und ich hhabs genauso aber ich hab ne frage: seh ich das richtig dass die 23 in diesem fall einmal übers die ganze tabelle "geschoben" wird bis man endlich 0 rausbekommt das noch frei is?

  13. #13
    Kenny's Avatar
    Title
    Special User
    Join Date
    Jan 2002
    Location
    wien 23
    Posts
    507
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @ fraka das is eine gute idee

    das brent-hashing hab ich auch nicht ganz gecheckt, habs mir gestern versucht zu überlegen

    also

    j1 = j + h2 (k) mod m

    j2 = j + h2 (k') mod m

    also das j ist die position die sich nach h1 ergeben würde oder wie ?

    und wenn die besetzt ist mit k' , dann muß man j1 und j2 berechnen ok

    und was dann? besonders verwirrt mich der satz:
    "ist platz j1 frei oder j2 belegt so fahre mit j1 fort wie in der ursprünglichen doublehshing methode" ????

    was ??? muß ich dann wieder irgendwas mit dem h1(k) + i h2(k) mod m berechnen, und wie ?

    könnt da irgendwer ein kurzes bsp machen wo man die funktionsweise sieht, oder in deutschen sätzen erklären ?

    danke
    ciao.Markus

    http://www.mworx.at - Markus Jerko Photography

  14. #14

    Title
    Principal
    Join Date
    Feb 2002
    Location
    Wien 23
    Posts
    50
    Thanks
    0
    Thanked 0 Times in 0 Posts
    HI!

    Ich versteh die Brent-Methode so:

    angenommen du hast die hashfunktionen

    h1 = j mod 5
    h2 = (j mod 3)+1

    und du fügst zuerst 2 und dann 4 ein, wo du h2 ja mal gar nicht brauchst.
    dann fügst du 7 ein, was auch den selben platz wie 2 kommen würde.

    Brent schaut jetzt, wo das Element, das schon in der Liste ist, hinkommen würde, wenn man drauf h2 anwenden würd, und wo das neue Element hinkommen würde.

    in dem Fall wäre
    j1 = 2 + h2(7) mod 5 = 4 und
    j2 = 2 + h2(2) mod 5 = 0

    der Absatz "Ist Platz j1 frei oder Platz j2 belegt, blabla..." heißt in dem Fall:
    j1 ist nicht frei, aber dafür j2, also kommt der 2er an eine neue Stelle (0), und der 7er an den Platz Nummer 2.

    Wäre jetzt aber z.B. der Platz 0 schon besetzt, bleibt der 2er wo er is, und für den 7er wird nach dem normalen Double Hashing weiterprobiert, d.h. du hupfst immer 2 weiter, bis du einen leeren Platz findest.

    Ist j1 gleich frei, kommt das neue Element gleich dorthin, egal ob j2 auch frei ist oder nicht.

    Ich hoffe, das war irgendwie verständlich.

    lg, Geli
    Last edited by Geli; 20-05-2002 at 16:14.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •