How can I evenly distribute individual keys in a hash table?

Question

I have this formula:

index = (a * k) % M 

which maps the number "k" from the input set K of different numbers to its position in the hash table. I was wondering how to write a program without brute force that finds such “M” and “a” so that “M” is minimal, and no collisions for a given set K.

Answer 1

If, instead of numerically multiplying, you can perform a logical calculation (and / or / not) , I think that the optimal solution (the minimum value of M) will be less than card(K) if you could get a function that binds each value of K (after ordering) with his position in the set.

Theoretically, it should be possible to write a truth table for such a relationship (bit to bit), and then simplify minterms through the Karnaugh table using the appropriate program. Depending on the desired number of bits, computational complexity would be available ... or not.

Answer 2

If a is coprime in M, then a * k = a * k 'mod M, if and only if k = k' mod M, so you can also use a = 1, up to M. This also covers all cases, when M is prime, since all numbers except 0 are then coprime to M.

If a and M are not compatible, then they have a common coefficient, say b, so a = x * b and M = y * b. In this case, everything that is multiplied by a will also be divisible by b mod M, and you can also work with mod y, not mod M, so nothing will work if you do not use it with M.

So, for this problem, you can save some time by leaving a = 1 and trying all possible values ​​of M.

If you, for example, using 32-bit integers and really computing not (a * k) mod M, but ((a * k) mod 2 ^ 32) mod M, you could find cases where values ​​other than 1, better than a = 1 due to what happens in (a * k) mod 2 ^ 32.