为字符串散列选择参数
Selecting parameters for string hashing
我最近在阅读一篇关于字符串哈希的文章。我们可以通过将字符串转换为多项式来散列字符串。
H(s1s2s3 ...sn) = (s1 + s2*p + s3*(p^2) + ··· + sn*(p^n−1)) mod M.
对p和M有什么约束才能降低碰撞概率？
A good requirement for a hash function on strings is that it should be difficult to find a
pair of different strings, preferably of the same length n, that have equal fingerprints. This
excludes the choice of M < n. Indeed, in this case at some point the powers of p corresponding
to respective symbols of the string start to repeat.
Similarly, if gcd(M, p) > 1 then powers of p modulo M may repeat for
exponents smaller than n. The safest choice is to set p as one of
the generators of the group U(ZM) – the group of all integers
relatively prime to M under multiplication modulo M.
我无法理解上述限制。选择 M < n 和 gcd(M,p) > 1 如何增加碰撞？有人可以用一些例子来解释这两个吗？我只需要对这些有一个基本的了解。
另外，如果有人能把重点放在M的上界和下界上，那就绰绰有余了。
以上事实摘自以下文章string hashing mit.
这些问题的 "correct" 答案涉及一定数量的数论，但查看一些极端情况以了解为什么约束可能有用通常会很有启发性。
例如，让我们看看为什么要 M ≥ n。作为极端情况，让我们选择 M = 2 和 n = 4。然后查看数字 p0 mod 2，p1 mod2，p2mod2，而p3mod2.因为有这里有四个数字，只有两个可能的余数，根据鸽巢原理，我们知道这些数字中至少有两个必须相等。为简单起见，我们假设 p0 和 p1 相同。这意味着散列函数将 return 对前两个字符已被交换的任意两个字符串使用相同的散列码，因为这些字符乘以相同的数量，这不是 属性 所希望的哈希函数。更一般地，我们想要 M ≥ n 的原因是值 p0, p1, ..., pn-1至少有被区分的可能性。如果 M < n，则 p 的幂太多，以至于它们都不是唯一的。
现在，让我们考虑一下为什么我们想要 gcd(M, p) = 1。作为一个极端的情况，假设我们选择 p 使得 gcd(M, p) = M（也就是说，我们选择 p = M ).那么
s0p0 + s1p1 + s2p2 + ... + sn-1pn-1 (mod M)
= s0M0 + s1M1 + s2M2 + ... + sn-1Mn-1 (mod M)
= s0
哎呀，这不好 - 这使得我们的哈希码正好等于字符串的第一个字符。这意味着如果 p 不与 M 互质（即，如果 gcd(M, p) ≠ 1），您 运行 某些字符成为哈希码 "modded out" 的风险，增加了碰撞概率。
How selecting M < n and gcd(M,p) > 1 increases collision?
在您的散列函数公式中，M 可能合理地用于将散列结果限制为特定位宽：例如M=216 用于 16 位哈希，M=232 用于 32 位哈希，M=2^64 用于 64 -位散列。通常，在实现中实际上不需要 mod/% 操作，因为使用所需大小的无符号整数进行哈希计算本质上会执行该功能。
我不推荐它，但有时您确实看到人们描述的散列函数是如此专一地与特定散列的大小 table 相关联，以至于他们 mod 将结果直接传给table尺寸。
您引用的文字说：
A good requirement for a hash function on strings is that it should be difficult to find a pair of different strings, preferably of the same length n, that have equal fingerprints. This excludes the choice of M < n.
这在三个不同的方面似乎有点愚蠢。首先，这意味着散列一段较长的文本需要一个非常长的散列值，而实际上选择 M 时最好考虑的是您需要散列的不同文本段的数量。
更具体地说，如果您有 V 个不同的值要使用良好的通用哈希函数进行哈希处理，那么如果您的哈希函数至少产生 V2[，您将大大减少哈希值的冲突。 =38=] 不同的哈希值。例如，如果您正在散列 1000 个值 (~210)，您希望 M 至少为 100 万（即至少 2*10 = 20 位散列值，即可以四舍五入到 32 位，但最好不要满足于 16 位）。阅读 Birthday Problem 以获得相关见解。
其次，给定 n 是字符数，潜在值的数量（即不同的输入）是任何特定字符可以采用的不同值的数量，n 次幂。前者可能有 26 到 256 个值，具体取决于散列是否只支持字母，或者说字母数字输入，或者标准与扩展 ASCII 和控制字符等，甚至更多的 Unicode。 "excludes the choice of M < n" 暗示 M 和 n 之间任何相关线性关系的方式都是虚假的；如果有的话，它是因为 M 下降到它越来越多地促进碰撞的不同潜在输入值的数量，但它又是 实际 不同输入的数量往往非常重要。
第三，"preferably of the same length n" - 为什么这很重要？据我所知，不是。
我对 templatetypedef 关于 gcd 的讨论没有什么要补充的。
我最近在阅读一篇关于字符串哈希的文章。我们可以通过将字符串转换为多项式来散列字符串。
H(s1s2s3 ...sn) = (s1 + s2*p + s3*(p^2) + ··· + sn*(p^n−1)) mod M.
对p和M有什么约束才能降低碰撞概率？
A good requirement for a hash function on strings is that it should be difficult to find a pair of different strings, preferably of the same length n, that have equal fingerprints. This excludes the choice of M < n. Indeed, in this case at some point the powers of p corresponding to respective symbols of the string start to repeat.
Similarly, if gcd(M, p) > 1 then powers of p modulo M may repeat for exponents smaller than n. The safest choice is to set p as one of the generators of the group U(ZM) – the group of all integers relatively prime to M under multiplication modulo M.
我无法理解上述限制。选择 M < n 和 gcd(M,p) > 1 如何增加碰撞？有人可以用一些例子来解释这两个吗？我只需要对这些有一个基本的了解。
另外，如果有人能把重点放在M的上界和下界上，那就绰绰有余了。 以上事实摘自以下文章string hashing mit.
这些问题的 "correct" 答案涉及一定数量的数论，但查看一些极端情况以了解为什么约束可能有用通常会很有启发性。
例如，让我们看看为什么要 M ≥ n。作为极端情况，让我们选择 M = 2 和 n = 4。然后查看数字 p0 mod 2，p1 mod2，p2mod2，而p3mod2.因为有这里有四个数字，只有两个可能的余数，根据鸽巢原理，我们知道这些数字中至少有两个必须相等。为简单起见，我们假设 p0 和 p1 相同。这意味着散列函数将 return 对前两个字符已被交换的任意两个字符串使用相同的散列码，因为这些字符乘以相同的数量，这不是 属性 所希望的哈希函数。更一般地，我们想要 M ≥ n 的原因是值 p0, p1, ..., pn-1至少有被区分的可能性。如果 M < n，则 p 的幂太多，以至于它们都不是唯一的。
现在，让我们考虑一下为什么我们想要 gcd(M, p) = 1。作为一个极端的情况，假设我们选择 p 使得 gcd(M, p) = M（也就是说，我们选择 p = M ).那么
s0p0 + s1p1 + s2p2 + ... + sn-1pn-1 (mod M)
= s0M0 + s1M1 + s2M2 + ... + sn-1Mn-1 (mod M)
= s0
哎呀，这不好 - 这使得我们的哈希码正好等于字符串的第一个字符。这意味着如果 p 不与 M 互质（即，如果 gcd(M, p) ≠ 1），您 运行 某些字符成为哈希码 "modded out" 的风险，增加了碰撞概率。
How selecting M < n and gcd(M,p) > 1 increases collision?
在您的散列函数公式中，M 可能合理地用于将散列结果限制为特定位宽：例如M=216 用于 16 位哈希，M=232 用于 32 位哈希，M=2^64 用于 64 -位散列。通常，在实现中实际上不需要 mod/% 操作，因为使用所需大小的无符号整数进行哈希计算本质上会执行该功能。
我不推荐它，但有时您确实看到人们描述的散列函数是如此专一地与特定散列的大小 table 相关联，以至于他们 mod 将结果直接传给table尺寸。
您引用的文字说：
A good requirement for a hash function on strings is that it should be difficult to find a pair of different strings, preferably of the same length n, that have equal fingerprints. This excludes the choice of M < n.
这在三个不同的方面似乎有点愚蠢。首先，这意味着散列一段较长的文本需要一个非常长的散列值，而实际上选择 M 时最好考虑的是您需要散列的不同文本段的数量。
更具体地说，如果您有 V 个不同的值要使用良好的通用哈希函数进行哈希处理，那么如果您的哈希函数至少产生 V2[，您将大大减少哈希值的冲突。 =38=] 不同的哈希值。例如，如果您正在散列 1000 个值 (~210)，您希望 M 至少为 100 万（即至少 2*10 = 20 位散列值，即可以四舍五入到 32 位，但最好不要满足于 16 位）。阅读 Birthday Problem 以获得相关见解。
其次，给定 n 是字符数，潜在值的数量（即不同的输入）是任何特定字符可以采用的不同值的数量，n 次幂。前者可能有 26 到 256 个值，具体取决于散列是否只支持字母，或者说字母数字输入，或者标准与扩展 ASCII 和控制字符等，甚至更多的 Unicode。 "excludes the choice of M < n" 暗示 M 和 n 之间任何相关线性关系的方式都是虚假的；如果有的话，它是因为 M 下降到它越来越多地促进碰撞的不同潜在输入值的数量，但它又是 实际 不同输入的数量往往非常重要。
第三，"preferably of the same length n" - 为什么这很重要？据我所知，不是。
我对 templatetypedef 关于 gcd 的讨论没有什么要补充的。