关于整数乘法、溢出和信息丢失

hashcode java overflow multiplication

2022-09-03 05:59:40

我正在阅读Joshua Bloch的《Effective Java》的第3章。在项目 8：当您覆盖等于时始终覆盖哈希码中，作者在其哈希函数中使用以下组合步骤：

result = 37 * result + c;

然后，他解释了为什么选择37（着重号是后加的）：

选择乘数37是因为它是一个奇数素数。如果它是偶数并且乘法溢出，信息将丢失，因为乘以二相当于移位。使用素数的优点不太清楚，但传统上使用素数来实现此目的。

我的问题是，为什么组合因子（37）是奇数很重要？乘法溢出不会导致信息丢失，而不管因子是奇数还是偶数？

答案 1

考虑一下当一个正值在以2为基数的表示中反复乘以2时会发生什么 - 所有设置的位最终都从末尾行进，留下零。

偶数乘数将导致哈希代码的多样性较小。

另一方面，奇数可能导致溢出，但不损失多样性。

答案 2

哈希码的目的是根据输入获得随机位（特别是较低的位，因为这些位通常使用得更多）

乘以2时，最低位只能是0，这缺乏随机性。如果乘以奇数，则最低位可以是奇数或偶数。

一个类似的问题是你在这里得到什么

public static void main(String... args) {
    System.out.println(factorial(66));
}

public static long factorial(int n) {
    long product = 1;
    for (; n > 1; n--)
        product *= n;
    return product;
}

指纹

每秒钟的数字是偶数，并且每隔一个是4的倍数，依此类推。