Ich habe diese Formel:
%Vor%, die eine Zahl 'k' von einer Eingabesatz K von verschiedenen Zahlen in ihre Position in einer Hashtabelle abbildet. Ich habe mich gefragt, wie man ein Programm ohne Brute-Force schreibt, das solche "M" und "a" findet, so dass "M" minimal ist und es keine Kollisionen für die gegebene Menge K gibt.
Wenn anstelle einer numerischen Multiplikation eine logische Berechnung (und / oder / nicht) durchführen könnte , denke ich, dass die optimale Lösung (Minimalwert von M) wäre em> so klein wie card(K) , wenn Sie eine Funktion erhalten könnten, die jeden Wert von K (einmal geordnet) mit seiner Position in der Menge in Beziehung setzt.
Theoretisch muss es möglich sein, eine Wahrheitstabelle für eine solche Relation (ein Bit) zu schreiben und dann die Minterms durch eine Karnaugh-Tabelle mit einem geeigneten Programm zu vereinfachen. Abhängig von der gewünschten Anzahl von Bits wäre die rechnerische Komplexität erschwinglich ... oder nicht.
Wenn a Co-Primzahl zu M ist, dann a * k = a * k 'mod M wenn, und nur wenn, k = k' mod M, so könnte man auch a = 1 verwenden, was immer mit- Primzahl für M. Dies deckt auch alle Fälle ab, in denen M Primzahl ist, weil dann alle Zahlen außer 0 Co-Primzahl zu M sind.
Wenn a und M nicht co-prim sind, dann teilen sie einen gemeinsamen Faktor, sagen wir b, also a = x * b und M = y * b. In diesem Fall ist alles, was mit a multipliziert wird, auch durch b mod M teilbar, und du könntest genauso gut mod modieren, nicht mod M, also gibt es nichts zu gewinnen, wenn man eine nicht co-Primzahl zu M benutzt.
Sie können also für das Problem, das Sie angeben, etwas Zeit sparen, indem Sie a = 1 belassen und alle möglichen Werte von M ausprobieren.
Wenn Sie z.B. 32-Bit-Ganzzahlen verwendend und wirklich nicht (a * k) mod M aber ((a * k) mod 2 ^ 32) mod M errechnend, könnten Sie Fälle finden, in denen Werte eines anderen als 1 besser als a = 1 sind wegen dem, was in (a * k) mod 2 ^ 32 passiert.
Tags und Links algorithm collections hashtable hash-collision