如何在哈希表中均匀分配不同的键？

Question

我有这个公式:

index = (a * k) % M

它将数字'k'从不同数字的输入集K映射到哈希表中的位置.我想知道如何编写一个非暴力程序,找到这样的'M'和'a',使'M'最小,并且给定的集合K没有碰撞.

Answer 1

如果您可以执行逻辑计算（和/或/非）而不是数字乘法，我认为最佳解决方案（M 的最小值）将尽可能小，就像card(K)您可以获得一个与 K 的每个值相关的函数一样（一旦订购）及其在集合中的位置。

理论上，必须可以为这样的关系编写一个真值表（一点点），然后通过适当的程序通过卡诺表简化小项。根据所需的位数，计算复杂性是否可以承受。