Divisions-Rest-Methode vs. Multiplikationsmethode
-
In meinem Script über Hash-Verfahren, findet sich folgender unbelegter Satz:
Eine empirische Untersuchung ergab, dass die Divisions-Rest-Methode der Multiplikationsmethode überlegen ist.
Warum ist das für Hash-Tabellen so? Im Script steht die ganze Zeit, dass man bei der Divisions-Rest-Methode vorsichtig mit der Größe von m sein muss (soll Prim sein, soll weit weg von 2^x liegen, etc.) das kann man sich bei der Multiplikationsmethode alles sparen. Warum also plötzlich andersrum?
MfG SideWinder
-
daß die bessere methode empfindlicher ist, ist doch nichts ungewöhnliches. quicksort ist ja auch schneller als heapsort und empfindlicher gegen schlechte eingangsdaten.
warum die divisionsrestmethode ein wenig netter ist? keine ahnung, ob das überhaupt jemand weiß. normalerweise steht bei sowas als fußnote "Don Knuth hat es ausgemessen".
-
Aus dieser Sicht, sieht's nicht mehr so ungewöhnlich aus. Danke.
Wenn ich noch eine Frage bzgl. Double-Hashing anhängen darf:
Tabellengröße m = 7
h1 = k mod 11
h2 = 2 + (k mod 5)Warum sind diese Hash-Funktionen nicht gut. Meine Antwort:
h1 übel, weil: mod 11 und dann mod 7 die 0, die 1, 2 und die 3 doppelt so oft belegt?
h2, keine Ahnung. Als Musterlösung haben wir h2 = 1 + (k mod m') wobei m' = m - 1 oder m' = m - 2
Ist 2 + nun sehr übel? Wahrscheinlich nicht. Aber mod 5? Ach, Herr Gott. Da steht alles einfach so drin. Wer soll diese Testfragen dann beantworten? *grml*
MfG SideWinder
MfG SideWinder
-
h2 ist schlecht, weil das Feld 1 nicht ohne rehash(habt ihr das überhaupt?) belegt werden kann da h2 Werte in [2;6] gibt.
Die Musterlösung verstehe ich nicht.
h2 = 1 + (k mod m') mit m' = m - 1
Gibt werte in [1;m] das ist gut, wenn modulo m danach ausgeführt wird, weil dann Werte in [0;m-1] raus kommen
h2 = 1 + (k mod m') mit m' = m - 2
Könnte gut sein, wenn die Arrayzählung bei 1 und nicht bei 0 beginnt, aber sonst keine Idee.//edit hatte mich oben bei h2 verrechnet. ehemals stand für den bereich [2;7] statt [2;6]
-
Tabellengröße m = 7
h1 = k mod 11
h2 = 2 + (k mod 5)Warum sind diese Hash-Funktionen nicht gut. Meine Antwort:
h1 übel, weil: mod 11 und dann mod 7 die 0, die 1, 2 und die 3 doppelt so oft belegt?ja, sehe ich genauso.
h2 bestimmt dann die sprungweite und die sollte teilerfremd zur tabellengröße sein und darf auf keinen fall 0 werden, also hier in [1;6] liegen. das wird durch die gegebene h2 erfüllt. außerdem sollte sie stark vom key abhängen, weshalb man m' möglichst groß wählt. ist auch erfüllt. ich sehe an h2 kein problem.
gut für h2 sind wohl 1+k%6, 1+k%5 und 2+k%5. würde ich meinen.
allerdings hab ich in echtem code noch nie 2+ gesehen, da steht immer nur 1+. vermutlich nur, damit das "if pos>7 then let pos=pos-7 : rem statt mod 7" seltener ausgeführt wird.
-
Danke ihr Beiden!
MfG SideWinder