如何在哈希表中均匀分布不同的键？
How can I evenly distribute distinct keys in a hashtable?
我有这个公式：
index = (a * k) % M
它将来自不同数字的输入集 K 中的数字 'k' 映射到它在哈希表中的位置。我想知道如何编写一个非暴力程序来找到这样的 'M' 和 'a' 以便 'M' 最小，并且给定的集合 K 没有冲突。
如果 a 与 M 互质，则 a * k = a * k' mod M 当且仅当 k = k' mod M，所以你也可以使用 a = 1，它始终与 M 互质。这也涵盖了 M 为质数的所有情况，因为除 0 之外的所有数字都与 M 互质。
如果a和M不是互质的，那么他们有一个共同的因素，比如说b，所以a = x * b和M = y * b。在这种情况下，任何乘以 a 的值也将被 b mod M 整除，您也可以使用 mod y，而不是 mod M，因此没有任何收获使用一个非互质的 M.
因此对于您陈述的问题，您可以通过保留 a=1 并尝试 M 的所有可能值来节省一些时间。
如果你是使用 32 位整数并且真正计算的不是 (a * k) mod M 而是 ((a * k) mod 2^32) mod M 你可能会发现这样的情况由于 (a * k) mod 2^32.
中发生的情况，除 1 之外的 a 值比 a=1 表现更好
如果，您可以执行逻辑计算（和/或/非）而不是数字乘法，我认为最优解（M 的最小值） 会 和 card(K) 一样小，如果你能得到一个函数将 K 的每个值（一旦排序）与其在集合中的位置相关联。
理论上，这样的关系（有点）一定可以写出真值table，然后通过卡诺Table 使用适当的程序。根据所需的位数，计算复杂度是否可以负担得起……或不可以。
我有这个公式：
index = (a * k) % M
它将来自不同数字的输入集 K 中的数字 'k' 映射到它在哈希表中的位置。我想知道如何编写一个非暴力程序来找到这样的 'M' 和 'a' 以便 'M' 最小，并且给定的集合 K 没有冲突。
如果 a 与 M 互质，则 a * k = a * k' mod M 当且仅当 k = k' mod M，所以你也可以使用 a = 1，它始终与 M 互质。这也涵盖了 M 为质数的所有情况，因为除 0 之外的所有数字都与 M 互质。
如果a和M不是互质的，那么他们有一个共同的因素，比如说b，所以a = x * b和M = y * b。在这种情况下，任何乘以 a 的值也将被 b mod M 整除，您也可以使用 mod y，而不是 mod M，因此没有任何收获使用一个非互质的 M.
因此对于您陈述的问题，您可以通过保留 a=1 并尝试 M 的所有可能值来节省一些时间。
如果你是使用 32 位整数并且真正计算的不是 (a * k) mod M 而是 ((a * k) mod 2^32) mod M 你可能会发现这样的情况由于 (a * k) mod 2^32.
中发生的情况，除 1 之外的 a 值比 a=1 表现更好如果，您可以执行逻辑计算（和/或/非）而不是数字乘法，我认为最优解（M 的最小值） 会 和 card(K) 一样小，如果你能得到一个函数将 K 的每个值（一旦排序）与其在集合中的位置相关联。
理论上，这样的关系（有点）一定可以写出真值table，然后通过卡诺Table 使用适当的程序。根据所需的位数，计算复杂度是否可以负担得起……或不可以。