Double Hashing

[Merlin]

Soll das m' der h2(k)-Funktion immer m-1 oder m-2 sein, oder soll es ebenfalls eine Primzahl sein, die dann halt kleiner als das urprüngliche m ist?

Oder muss es nur relativ prim sein, also dass m' unser m nicht teilt?

Also wenn m z.B 23 ist, wähle ich 22/21 oder ist es besser eine Primzahl wie z.B 17 herzunehmen ?

[ein_stein2000]

also in meinem buch (algorithmen und datenstrukturen, t. ottmann, p. widmayer) steht drinat:

"ist m eine primzahl und h(k) = k mod m, so erfüllt h'(k) = 1 + k mod (m-2) die obige anforderungen (das ist besser als 1 + k mod (m-1), weil m-1 gerade ist)" ... mit obiger anforderung is nur gemeint, dass in h'(k) eine gewisse häufung auftreten kann, die in h(k) (wenn prim) nicht auftreten kann ...

also kurz: es is bessa m-2 zu nehmen, weil du dan wieda ah ungerade zahl hast (in der annahme, dass m prim is)

[grassi3000]

Ich hab mich mal ein wenig gespielt, und bei einem speziellen Fall ist es besser, wenn das m' = m ist. Nehme ich m'= m-1 oder m'= m-2 dann brauche ich mehr iterationen, bis ich einen freien platz finde.

Ist es nun zulässig, dass das m' auch = m ist, oder muss es entweder m-1 oder m-2 sein?

[ein_stein2000]

alsso i hab mir dazugeschrieben: "es muss immer gelten m'<m"

[Silvester]

Das Problem ist ja folgendes: wenn man die 2. Hash-Funktion ganz normal wie die erste behandelt also irgendwas mod m, dann kann diese unter Umständen auch den Wert 0 annehmen, was ja bei der 1. Hash-Funktion auch sein kann und auch erwünscht ist, weil ja sonst nie der Index 0 gefüllt werden würde.
Die 2. Hash-Funktion macht aber die Schrittweite für die Durchmusterung und Schrittweite 0 ist nicht gut, wie man sich leicht überlegen kann.
Nimmt man aber (irgendwas mod m-1) + 1 so kann das nie 0 sein und somit ist gesichert, dass auch tatsächlich eine Durchmusterung stattfindet.
Und analog dazu geht natürlich auch 2 + (irgendwas mod m-2).