在覆盖 hashCode（）时使用较大的素数作为乘数

hashcode java hash primes

2022-09-04 21:27:49

在过去的几个小时里，我一直在阅读有关哈希码函数的信息，并积累了一些关于在自定义哈希码实现中使用素数作为乘数的问题。如果我能就以下问题获得一些见解，我将不胜感激：

在对@mattb的答案的评论中，@hstoerr主张使用更大的素数（如524287）而不是公共素数31。我的问题是，给定一对或多个元素的哈希码函数的以下实现：

@Override
public int hashCode() {
    final int prime = 31;
    int hash1 = (pg1 == null) ? 0 : pg1.hashCode();
    int hash2 = (pg2 == null) ? 0 : pg2.hashCode();
    return prime * (hash1 ^ hash2);
}

这是否会导致返回的溢出，如果是一个大数字？intprime

假设溢出不是问题（JVM执行自动转换），那么进行位移而不是强制转换会更好吗？
我认为哈希码函数的性能会根据哈希码的复杂性而有很大差异。质数乘数的大小不会影响性能吗？
在自定义哈希码函数中使用多个素数而不是单个乘数是否更好/更智能/更快？如果没有，还有其他优势吗？请参阅以下示例，该示例来自@jinguy对相关问题的回答：
```
public int hashCode() {
    return a * 13 + b.hashCode() * 23 + (c? 31: 7);
}
```

其中是一个，是一个并且是。aintbStringcboolean

像然后使用的东西怎么样？这是我在另一个问题中看到的，但它并没有真正解释为什么这样做是一个好主意。long lhash = prime * (hash1 ^ hash2);(int)((lhash >> 32) ^ lhash)

答案 1

提前为小说道歉。随时提出建议或直接编辑。--切特

有溢出，但不是例外。

危险不是来自失去准确性，而是失去射程。让我们使用一个荒谬的例子，其中“素数”是2的大幂，为了简洁起见，8位无符号数字。假设是 255：(hash1 ^ hash2)

        "prime": 1000 0000
(hash1 ^ hash2): 1111 1111

在括号中显示截断的数字，我们的结果是：

        product: [0111 1111] 1000 0000

但是乘以128与向左移动7位是一样的。所以我们知道，无论的值如何，乘积的最不重要的地方将有七个零。因此，如果为奇数（最低有效位 = 1），则乘以 128 的结果将始终为 128（截断较高数字后）。如果是偶数（LSB为0），则乘积将始终为零。(hash1 ^ hash2)(hash1 ^ hash2)(hash1 ^ hash2)

这扩展到更大的位大小。一般的观点是，如果“”的下位是零，则您正在执行移位（或多次移位+和）操作，该操作将在较低位中为您提供零。乘法乘积的范围将受到影响。prime

但是，让我们尝试使“”变得奇怪，以便最不重要的位始终为1。考虑将其分解为移位/添加操作。的未移动值将永远是总结之一。现在，通过偶数“”乘法器移入保证无用的最低有效位将至少基于原始值的位进行设置。prime(hash1 ^ hash2)prime(hash1 ^ hash2)

现在，让我们考虑一个值，它实际上是素数。如果它超过2，那么我们知道它是奇怪的。因此，较低的位并没有被转移到无用状态。通过选择足够大的素数，您可以在输出值范围内获得比使用较小素数更好的分布。prime

尝试使用 8443 （）和 59 （）进行一些 16 位乘法的练习。它们都是素数，59 的下位与 65531 的下位匹配。例如，如果 hash1 和 hash2 都是 ASCII 字符值（0 .. 255），则（hash1 ^ hash2） * 59 的所有结果都将<= 15045。这意味着大约 16 位数字的哈希值范围（0..65535）的 1/4 未使用。0010 0000 1111 10110000 0000 0011 1011

但到处都是地图。如果低至 8，则溢出。它使用所有16位，即使对于非常小的输入数字也是如此。即使输入数字在相对较小的范围内，整个范围内哈希值的聚类也要少得多。(hash1 ^ hash2) * 8443(hash1 ^ hash2)

假设溢出不是问题（JVM执行自动转换），那么进行位移而不是强制转换会更好吗？

很可能不是。无论如何，JVM都应该在主机处理器上转换为有效的实现。整数乘法应在硬件中实现。如果没有，JVM负责将操作转换为对CPU合理的东西。整数乘法的情况很可能已经高度优化。如果在给定的 CPU 上以移位加法的形式更快地完成整数乘法，则 JVM 应以这种方式实现它。但是，编写JVM的人不太可能注意注意多个移位和加法操作可以组合成单个整数乘法的情况。

我认为哈希码函数的性能会根据哈希码的复杂性而有很大差异。质数乘数的大小不会影响性能吗？

哈哈在硬件中执行的操作是相同的，无论大小，设置的位数等如何。这可能是几个时钟周期。它将因特定的 CPU 而异，但无论输入值如何，都应是常量时间操作。

在自定义哈希码函数中使用多个素数而不是单个乘数是否更好/更智能/更快？如果没有，还有其他优势吗？

只有当它降低了碰撞的可能性时，这取决于你使用的数字。如果您的哈希代码依赖于和并且它们位于同一范围内，则可以考虑使用不同的素数或移动其中一个输入值以减少位之间的重叠。由于您依赖于他们的个人哈希代码，而不是直接他们的值，因此可以合理地假设他们的哈希代码提供了良好的分布等。AB

想到的一个因素是您是否希望的哈希代码与不同。如果您的哈希函数以相同的方式处理和，则 .如果这是你想要的，那么一定要使用相同的乘数。它不是，使用不同的乘数是有意义的。(x, y)(y, x)ABhash(x, y) = hash(y, x)

像然后使用的东西怎么样？这是我在另一个问题中看到的，但它并没有真正解释为什么这样做是一个好主意。long lhash = prime * (hash1 ^ hash2);(int)((lhash >> 32) ^ lhash)

有趣的问题。在 Java 中，long 是 64 位，int 是 32 位。因此，这将使用所需位数的两倍生成哈希值，然后从高位和低位组合中派生结果。

如果将一个数字乘以素数，并且最下面的位都是零，那么乘积的最低位也将是所有零。这很容易看出 -- 如果你乘以，比如说，和，那么乘积可以表示为两个班次操作的总和。阿尔布npknkn * pn = 0011 0000p = 0011 1011

00110000 * p = 00100000 * p + 00010000 * p
             = p << 5 + p << 4

采用并使用无符号 8 位整数和 16 位长整型，下面是一些示例。p = 59

 64: 0011 1011 * 0100 0000 = [ 0000 1110 ] 1100 0000 (192)
128: 0011 1011 * 1000 0000 = [ 0001 1101 ] 1000 0000 (128)
192: 0011 1011 * 1100 0000 = [ 0010 1100 ] 0100 0000 (64)

通过仅删除结果的高位，当非素数乘数的低位全部为零时，生成的哈希值的范围受到限制。在特定上下文中，这是否是一个问题，嗯，是特定于上下文的。但对于一般的哈希函数，最好避免限制输出值的范围，即使输入数字中存在模式也是如此。在安全应用程序中，避免任何会让某人根据输出中的模式对原始值进行推断的东西变得更加重要。只需取低位即可显示一些原始位的确切值。如果我们假设该操作涉及将输入数与大素数相乘，那么我们知道原始数在右侧的零数与哈希输出一样多（因为素数最右边的位是1）。

通过将高位与低位进行XON运算，输出的一致性降低。更重要的是，根据这些信息对输入值进行猜测要困难得多。根据XOR的工作原理，它可能意味着原始低位为0，高位为1，或者原始低位为1，高位为0。

 64: 0011 1011 * 0100 0000 = 0000 1110 1100 0000 => 1100 1110 (206)
128: 0011 1011 * 1000 0000 = 0001 1101 1000 0000 => 1001 1101 (157)
192: 0011 1011 * 1100 0000 = 0010 1100 0100 0000 => 0110 1100 (204)

答案 2

溢出不是问题。无论如何，哈希都被限制为一个狭窄的值集。
您发布的第一个哈希函数不是很好。相反，在大多数情况下，做'会减少碰撞的次数。return (prime * hash1) ^ hash2;
乘以单个单词int通常非常快，乘以不同数字之间的差异可以忽略不计。此外，执行时间与函数 anyay 中的其他所有内容相比相形见绌
对每个部件使用不同的素乘数可以降低碰撞的风险。

在覆盖 hashCode（） 时使用较大的素数作为乘数

在覆盖 hashCode（）时使用较大的素数作为乘数