c - 字符串的哈希算法

Question

我正在阅读 Robert Sedwick 的 C++ 算法哈希

字符串键的散列函数的实现涉及键中每个字符的一次乘法和一次加法。如果我们用 128 替换常量 127，程序将使用 Horner 的方法简单地计算与 key 的 7 位 ASCII 表示对应的数字除以表大小时的余数。如果表大小是 2 的幂或 2 的倍数，则以 127 为底的素数可以帮助我们避免异常。

int hash(char *v, int M)
    { int h = 0, a = 127;
      for (; *v != 0; v++)
        h = (a*h + *v) % M;
      return h;
    }

理论上理想的通用散列函数是这样一个，即大小为 M 的表中两个不同键之间发生冲突的几率恰好为 1/M。可以证明，程序 14.1 中的系数 a 使用一系列不同的随机值，而不是固定的任意值，可以将模块化哈希变成通用哈希函数。然而，为 key 中的每个字符生成新随机数的成本可能会令人望而却步。程序 14.2 展示了一个实用的折衷方案:我们通过生成一个简单的伪随机序列来改变系数。

总而言之，要将散列用于抽象符号表实现，第一步是扩展抽象类型接口(interface)以包含将键映射到小于表大小 M 的非负整数的散列操作。直接实现

内联 int hash(Key v, int M) { 返回 (int) M*(v-s)/;

完成值 s 和 t 之间的浮点键的工作；对于整数键，我们可以简单地返回 v % M。如果 M 不是素数，哈希函数可能会返回

(int) (.616161 * (float) v) % M

或类似整数计算的结果，例如

(16161 * (unsigned) v) % M.

我的问题是，如果表格大小是 2 的幂或 2 的倍数，作者的意思是素数基数 127 如何帮助我们避免异常？

1. authorm 所说的“对于整数键，我们可以简单地返回 v % M”是什么意思？

2. 作者所说的“如果 M 不是素数，哈希函数可能返回”是什么意思

(int) (.616161 * (float) v) % M

或类似整数计算的结果，例如

(16161 * (unsigned) v) % M.

作者是如何想出 .616161 和 16161 的？

通过简单的例子请求帮助理解

Answer 1

首先，基数必须与字长互质，否则字符串的第一个字符对哈希值没有贡献；

例如一=256；字符串“AABA”、“AAABA”、“XYZAABA”都将产生相同的散列，因为中间变量 h 是以 2^32 为模计算的。

当每个字符只使用 7 位时，它会稍微复杂一些，但原理是成立的。

• 对于整数键，0<= v <2^32，M = table_size(M 是素数)，v % M 映射 v 的完整范围，同时考虑到 v 中的所有位。

• 在取模 M 之前，将整数 v 乘以 float 0.616161，保证 中的位发生某种扰乱em>v。否则，就像在第一个示例中一样，如果 M=100，会将所有值 1001、101、201、3412341234101 映射到同一个槽，忽略最多 90% 的变量位。