algorithm - 为什么合数不适合除法散列？

Question

这是我关于 stackflow 的第一个问题。如您所知，我是学习算法和数据结构的新手。

当使用除法方法创建哈希函数(即 h(k) = k mod m)时，建议(例如 CLRS)使用不太接近 2 的幂的质数作为除数 m .有人可以向我解释为什么选择 m 为复合数是错误的吗？

Answer 1

考虑如果 m 是偶数并且所有 k 值都是偶数的情况。那么，哈希值也将全部为偶数。

例如，考虑 m=6 散列偶数的情况:

Input values:  0, 2, 4, 6, 8, 10, 12, 14, 16, ...
Hash values:   0, 2, 4, 0, 2,  4,  0,  2,  4, ...

如果您将这些散列值用作表的索引，那么表的一半将未被使用。另一方面，如果 m 是素数，您将获得均匀分布的哈希值，即使输入值都具有公因数也是如此。

考虑相同的输入值，但 m=7:

Input values:  0, 2, 4, 6, 8, 10, 12, 14, 16, ...
Hash values:   0, 2, 4, 6, 1,  3,  5,  0,  2, ...

尽管输入值都是偶数，但哈希值仍然均匀分布在 [0..6] 上。

总而言之，如果 m 是素数，那么即使所有输入值都可以整除一个公共(public)素数(m 除外)，您仍然会得到均匀分布的哈希值。