hash - 什么时候适合使用简单的模数作为散列函数？

Question

我需要从一个 32 位数字创建一个 16 位哈希，并且我试图确定一个简单的模数 2^16 是否合适。

哈希将用于 2^16 条目哈希表中，以便快速查找 32 位数字。

我的理解是，如果数据空间的分布相当均匀，那么简单的 mod 2^16 就可以了——它不应该导致太多的冲突。

在这种情况下，我的 32 位数字是修改后的 adler32 校验和的结果，使用 2^16 作为 M。

所以，从一般意义上说，我的理解是否正确，如果我的数据分布均匀，可以使用简单的 mod n（其中 n 是哈希表大小）作为哈希函数？

具体来说，adler32 会为此提供足够随机的分布吗？

Answer 1

是的，如果您的 32 位数字均匀分布在所有可能的值上，那么其中的一个模数也将均匀分布在 n 个可能的值上。

修改后的校验和算法的结果是否均匀分布是一个完全不同的问题。这将取决于您应用算法的数据是否有足够的数据来滚动总和数次。如果您将该算法应用于不翻转总和的短字符串，则结果将不会均匀分布。

如果你想要一个哈希函数，那么你应该使用一个哈希函数。Adler-32 和任何 CRC 都不是一个好的散列函数。公共领域中有许多非常快速和有效的哈希函数。你可以看看CityHash。