Double Hasing

  • 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

  • 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

  • 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

  • Zitat

    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...

  • 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?

  • 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

  • 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

  • @ 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 :)

  • 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