Double Hashing 4 Dummies!

    Hilfe, ich kenne mich schon wieder nicht aus. Dieses mal beim Double Hashing aus der Prüfung vom 19.10.2007.


    Leider komm ich überhaupt nicht weiter. Ich weis zwar wie man die einzelnen Elemente einfügt, aber sobald es zu einer Kollision kommt, benutz ich die zweite funktion und wenn da auch eine Kollision ist, dann weiss ich überhaupt nicht mehr weiter. Hilfe! Könnte jemand dieses Beispiel durchrechnen. Es würde vieles klarstellen. Danke

    äähhmm....


    Code
    1. [B]Stoff:[/B] Skriptum Kapitel 1 (Einführung, Analyse von Algorithmen) bis inklusive
    2. Kapitel 2 (Sortieren).

    In meinem Skriptum kommen HashFunktionen erst im 5.Kapitel?
    Die haben doch nicht das ganze Skriptum komplett umgestellt? :omg:
    --> Was ist jetzt genau PrüfungsStoff?
    DoubleHashing zählt da nicht dazu afaik


    EDIT:
    DoubleHashing:
    du hast ja dein h1(k) = (k mod m) und dein h2(k)= i*[1+(k mod m´)]
    Sollte die Pos. in der Hashtabelle schon besetzt sein, in der du die Zahl einsetzen willst, verwendest du h2 & berechnest die neue Position. (mit i = 1)
    Auf die neue Position durch h2 kommst du, indem du den Wert der dir bei h2 rauskommt mit der Position wo die Zahl ürsprünglich hinkommen sollte addierst.
    Ist jedoch auch dieser Position wieder belegt, nimmst du wieder h2 her und erhöhst das i um 1. Dieser Wert wieder addiert mit der ursprünglichen Position = neue Position ... etc. pp
    Sollte dir eine Position rauskommen die "über" deiner Hashtable liegt z.B. HashtabelGrösse = 5 und die neue berechnete Position sollte 7 sein. Dann gehst du über die letzte Pos. deiner Table raus & zählst quasi bei der "nullten" Position weiter --> die zahl würde dann an Stelle 1 kommen (weil Position 0 = 6 und Pos 1 = 7)


    Brustvergrößerung durch Handauflegen!
    Mache auch Hausbesuche- rund um die Uhr!
    Näheres bitte bei PM!
    :shinner:

    Ich schliesse mich der Frage an, und versuche trotzdem eine Lösung zu posten. Natürlich weiß ich nicht ob das so richtig ist...


    h(k,i) = (h1(k) + i * h2(k)) mod m
    Einfügen von 7: k = 7, m = 7, i = 0:
    (2*7 + 3)mod7 + 0 * () = 3 .... 3 ist belegt, also nochmals mit i=1:
    ((2*7 + 3)mod7 + 1 * (7 mod 5) + 2) mod7 = 0 .... 0 ist belegt, also nochmals mit i=2:
    ((2*7 + 3)mod7 + 2 * (7 mod 5) + 2) mod7 = 2 .... 2 ist frei, somit bin ich fertig mit double hashing...


    Stimmt das so, oder habe ich das falsch in Erinnerung?

    ... So I open my door to my enemies
    And I ask could we wipe the slate clean
    But they tell me to please go fuck myself
    You know you just can't win ...

    is richtig... aber trotzdem


    HASH-FUNKTIONEN SIND NICHT PRÜFUNGSSTOFF DES 1.TESTS???? ODER????


    Ersuche um Aufklärung.... weil wenn doch, hab ich noch ne lange Nacht vor mir! :shinner:


    Brustvergrößerung durch Handauflegen!
    Mache auch Hausbesuche- rund um die Uhr!
    Näheres bitte bei PM!
    :shinner:

    thx 4 info - wußte nicht das Nebentermin von der VOPrüfung auch ist.
    dann kann ich mir ja den Angstschweiß wieder von der Stirn wischen! :devil:


    Brustvergrößerung durch Handauflegen!
    Mache auch Hausbesuche- rund um die Uhr!
    Näheres bitte bei PM!
    :shinner:


    Ich denke nicht dass das richtig ist, denn die Double hasing formel lautet:


    h(k,i) = (h1(k) + i*h2(k)) mod m


    also müsste man das oben so formulieren:


    [ ((2*7 + 3) mod 7) + 2*((7 mod 5)+2) ] mod 7 = (3 + 8) mod 7 = 4... belegt......


    Kann das irgendwer bestätigen?