作为值的线性组合的哈希函数有多好？
How good is hash function that is linear combination of values?
我正在阅读有关散列的文本，我发现 char 字符串的朴素散列码可以实现为多项式散列函数
h(S0,S1,S2,...SN-1) = S0*A^N-1 + S1*A^N-2 + S2*A^N-3 ..... SN -1*A^0。其中 Si 是索引 i 处的字符，A 是某个整数。
但是我们不能直接求和为
h(S0,S1,S2,...SN-1) = S0*(N)+S1*(N-1)+S2*(N-2) ...... SN- 1*1。
我认为这个函数也很好，因为两个值 2*S0+S1 != 2*S1+S0（它们是反向的）没有散列为相同的值。但是我在任何地方都找不到这种哈希函数
线性哈希函数的问题是更容易产生冲突。
考虑一个包含 3 个字符的字符串：S0、S1、S2。
建议的哈希码为 3 * S0 + 2 * S1 + S2。
每次我们将 char S2 减二（例如 e --> c），并将 char S1 增加一（例如 m --> n)，我们得到相同的哈希码。
即使只有可以如此轻松地描述保留哈希的操作这一事实也会引起警觉（因为某些算法可能会以这种方式精确处理字符串）。作为更极端的情况，考虑只对字符求和。在这种情况下，原始字符串的所有变位词都会生成相同的哈希码（因此该哈希值在处理变位词的应用程序中将无用）。
假设我们使用 30 个字符的字符串。那不长，但也没有短到纯粹因为字符串太短而出现散列问题。
权重总和为 465 (1+2+...+30)，可打印的 ASCII 字符使最大哈希值为 58590，通过“~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~”。有更多可能的 30 个字符的可打印 ASCII 字符串（9530 ≈ 2E59），但它们都散列到 0 到 58590 的范围内。自然你不能实际上 同时拥有那么多字符串，但你可以拥有比 58590 多得多的字符串，这将保证仅基于计数就会发生冲突（当然很可能会更快发生）。
最大哈希增长缓慢，在使用 32 位整数的整个范围之前，您需要 3400 万个字符的字符串。
另一种方式，乘以 A 的幂（这可以用 Horner 的方案进行评估，因此不需要显式计算幂，它仍然只需要每个字符的加法和乘法，尽管天真的方法不是计算该散列的最快方法），没有这个问题。 A 的幂很快变大（并开始回绕，只要 A 是奇数就可以），因此 30 个字符的字符串很有可能覆盖您正在使用的任何整数类型的整个范围。
我正在阅读有关散列的文本，我发现 char 字符串的朴素散列码可以实现为多项式散列函数
h(S0,S1,S2,...SN-1) = S0*A^N-1 + S1*A^N-2 + S2*A^N-3 ..... SN -1*A^0。其中 Si 是索引 i 处的字符，A 是某个整数。
但是我们不能直接求和为
h(S0,S1,S2,...SN-1) = S0*(N)+S1*(N-1)+S2*(N-2) ...... SN- 1*1。
我认为这个函数也很好，因为两个值 2*S0+S1 != 2*S1+S0（它们是反向的）没有散列为相同的值。但是我在任何地方都找不到这种哈希函数
线性哈希函数的问题是更容易产生冲突。
考虑一个包含 3 个字符的字符串：S0、S1、S2。 建议的哈希码为 3 * S0 + 2 * S1 + S2。
每次我们将 char S2 减二（例如 e --> c），并将 char S1 增加一（例如 m --> n)，我们得到相同的哈希码。
即使只有可以如此轻松地描述保留哈希的操作这一事实也会引起警觉（因为某些算法可能会以这种方式精确处理字符串）。作为更极端的情况，考虑只对字符求和。在这种情况下，原始字符串的所有变位词都会生成相同的哈希码（因此该哈希值在处理变位词的应用程序中将无用）。
假设我们使用 30 个字符的字符串。那不长，但也没有短到纯粹因为字符串太短而出现散列问题。
权重总和为 465 (1+2+...+30)，可打印的 ASCII 字符使最大哈希值为 58590，通过“~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~”。有更多可能的 30 个字符的可打印 ASCII 字符串（9530 ≈ 2E59），但它们都散列到 0 到 58590 的范围内。自然你不能实际上 同时拥有那么多字符串，但你可以拥有比 58590 多得多的字符串，这将保证仅基于计数就会发生冲突（当然很可能会更快发生）。
最大哈希增长缓慢，在使用 32 位整数的整个范围之前，您需要 3400 万个字符的字符串。
另一种方式，乘以 A 的幂（这可以用 Horner 的方案进行评估，因此不需要显式计算幂，它仍然只需要每个字符的加法和乘法，尽管天真的方法不是计算该散列的最快方法），没有这个问题。 A 的幂很快变大（并开始回绕，只要 A 是奇数就可以），因此 30 个字符的字符串很有可能覆盖您正在使用的任何整数类型的整个范围。