hashing - verWIRRUNG nach brent ?

  • das brent-hashing hab ich noch 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 einfach 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 das sieht, oder in deutschen sätzen erklären ?


    danke :)

  • hab mir das auch gestern überlegt,
    kann das so sein?
    also ich will etwas einfügen. Ich berechne den Hash1.
    Dann merk ich das dort schon etwas ist. Also berechne ich den Hash2 von beiden elementen. Wenn dann der Hash2 code von dem alten element auf eine unbenutzte stelle zeigt, wird das alte element auf die vom hash2 berechnete Stelle gesetzt und das einzufügende Element auf die stelle des alten elements.
    Wenn aber der hash2 von dem alten element besetzt ist, der hash2 vom einzufügenden El aber nicht mach normales DoubleHashing.


    sicher bin ich mir aber auch net, soll der georg kraml das morgen nochmal erklären :)

  • HI!


    Ich hab das zwar in einem Threat zur VO schon mit einem Beispiel versucht zu erklären, aber hier halt noch mal:


    wenn j1 frei ist, dann kommt das neue Element dort auf alle Fälle hin.
    Ist j1 besetzt, j2 aber nicht, kommt das alte Element auf j2.


    Sind beide besetzt, geht man für das neue Element die Sondierungsreihenfolge nach h2 durch. j1 ist ja praktisch schon der erste Schritt, dann geht's immer weiter.


    !!!


    Was mir aber nicht ganz klar ist, ist ob man das dann jedes Mal wiederholt, wenn man auf einen besetzten Platz stößt. Im Text heißt's zwar "nach der ursprünglichen Hashing-Methode", was ja heißt, ich such einfach nach einem freien Platz, in der Sondierungsreihenfolge.


    Wenn ich mir den Alg 36 aber anschau, dann steht dort doch, dass ich bei jedem neuen besetzten Platz wieder j1 und j2 berechne.


    ???


    lg, Geli