Hashing



  • Guten Abend, ich habe mal eine allgemeine Frage zu Hashing bzw zu dem Sondierungsschritt.

    Nehmen wir mal an wir haben eine Zeichenkette gegeben und einen Schlüssel
    Nun haben wir noch einen Array der Länge m=9 gegeben

    als Schlüssel k nehmen wir mal k=4
    Zeichenkette soll sein "Gebäude"

    Sondiereungsfunktion: s(j,k)=(k*(j+2)) mod m

    doch wie berechne ich jetzt den Sondierungsschritt j?

    quasi hätte ich: s(j,4)=(4*(j+2)) mod 9

    kann mir einer erklären wie ich auf dieses j komme?

    LG



  • Meinst Du doppeltes Hashing?

    j wird einfach hochgezählt, bis Du ein leeres Bucket findest.



  • Ich weiß um ehrlich zu sein nicht ob es ein doppeltes ist.
    Laut Wikipedia ist ein doppeltes so definiert:

    h_i(x)=( h(x)+h'(x)*i)) mod m

    Bei uns steht Multiplikatives Sondieren:

    Das Problem ist was meinst du mit hochzählen bis ein Bucket kommt? Was zähle ich hoch? Mein j ist ja nicht gegeben wie soll ich es hochzählen? j+1 j+2 usw?

    LG



  • Du startest mit j = 1 und zählst j dann hoch.
    Wobei die Formel (k*(j+2)) mod m problematisch ist. Wenn k zufällig mal ein Vielfaches von m ist, und die erste Position nicht gleich frei, dann hast du halt ein bisschen ein Problem.



  • ok..

    also machen wir mal anhand eines Übungsblattes:

    anderes Beispiel:

    s(j,k)=(k*(j+1)) mod 7

    Tim als Zeichenkette und Schlüssel k=4
    da kommt j=2 laut lösung
    aber wieso?

    LG



  • capri03 schrieb:

    Tim als Zeichenkette und Schlüssel k=4
    da kommt j=2 laut lösung
    aber wieso?

    Vermutlich weil du die Angabe nicht vollständig wiedergegeben hast, aus der hervorgeht dass Platz 4 (j = 1) schon belegt ist?



  • hustbaer schrieb:

    Du startest mit j = 1 und zählst j dann hoch.
    Wobei die Formel (k*(j+2)) mod m problematisch ist. Wenn k zufällig mal ein Vielfaches von m ist, und die erste Position nicht gleich frei, dann hast du halt ein bisschen ein Problem.

    Die Formel gibt richtig Gas, wenn m ein oberer Primzahlenzwilling ist. Und dafür könnte man ja sorgen.



  • Was wird beim Fall k == m besser wenn m ein oberer Primzahlenzwilling ist?



  • hustbaer schrieb:

    Was wird beim Fall k == m besser wenn m ein oberer Primzahlenzwilling ist?

    Nix. Hab mich verlesen.


Log in to reply