Doppel Hashing in offener Adressierung, welche Hash-Funktion und Tabellenlänge

Question

In Cormen Buch "Introduction to Algorithms" ich, dass Doppel-Hashing lesen (in offener Adressierung) Funktion ist in Form von:

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

wo k ist ein Schlüssel, i ist ein nächster Index im Falle einer Kollision, m ist die Tabellenlänge und hX sind Hash-Funktionen.

Er sagt, dass das Hauptproblem beim Double Hashing ist, alle Indizes in der Tabelle zu verwenden. Um dieses Problem zu lösen, sollten wir setzen m auf die Leistung von 2 und h2 Funktion sollte ungerade Werte zurückgeben. Warum (ich kann ihn nicht erklären sehen)

Answer 1

Die allgemeine Regel ist, dass Modulo m, h_2(k) wiederholt ist ein Zyklus, der mit der Periode m/GCD(m, h_2(k)) wiederholt. Wenn es keine gemeinsamen Faktoren zwischen m und h_2(k) gibt, wird es mit der Periode m wiederholt, was bedeutet, dass Sie alle m Indizes erreichen können. Sie wollen also keine gemeinsamen Faktoren.

Die Regel "keine gemeinsamen Faktoren" wird leicht erfüllt, indem m eine Potenz von 2 und h_2(k) ungerade gemacht wird.