java - 覆盖 hashCode() 时使用更大的素数作为乘数

Question

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

在对 @mattb's answer 的评论中在这里，@hstoerr 提倡使用更大的素数(例如 524287)而不是公共(public)素数 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);
}

这不会导致返回的 int 溢出如果 prime是大数吗？

假设溢出不是问题(JVM 执行自动转换)是不是执行位移而不是转换更好？

我想 hashcode 函数的性能会因 hashcode 的复杂性而显着不同。素数乘数的大小不影响性能吗？

在自定义哈希码函数中使用多个素数而不是单个乘数是否更好/更智能/更快？如果没有，是否还有其他优势？请参阅下面来自@jinguy 对 a relevant question 的回答中的示例:

public int hashCode() {
    return a * 13 + b.hashCode() * 23 + (c? 31: 7);
}

哪里 a是 int , b是 String和 c是 boolean .

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

Answer 1

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

有溢出，但也不异常(exception)。

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

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

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

        product: [0111 1111] 1000 0000

但是乘以 128 与左移 7 位相同。所以我们知道无论 (hash1 ^ hash2) 的值是多少，乘积的最低位将有七个零。所以如果 (hash1 ^ hash2)是奇数(最低有效位 = 1)，那么乘以 128 的结果将始终为 128(截断高位后)。如果 (hash1 ^ hash2)是偶数(LSB 为 0，那么乘积将始终为零。

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

但是让我们尝试将“ prime”设为奇数，以便最低有效位始终为 1。考虑将其分解为移位/加法操作。 (hash1 ^ hash2) 的未移位值将永远是被加数之一。由偶数“ prime”乘法器移入保证无用的最低有效位现在将至少根据原始 (hash1 ^ hash2) 中的位进行设置。值(value)。

现在，让我们考虑一个值 prime这实际上是素数。如果大于 2，则我们知道它是奇数。所以低位还没有变成无用。通过选择一个足够大的素数，与较小的素数相比，您可以在输出值范围内获得更好的分布。

使用 8443 ( 0010 0000 1111 1011 ) 和 59 ( 0000 0000 0011 1011 ) 尝试一些 16 位乘法练习。它们都是质数，59的低位与65531的低位匹配。例如，如果hash1和hash2都是ASCII字符值(0 .. 255)，那么(hash1 ^ hash2) *的所有结果59 将 <= 15045。这意味着 16 位数字的散列值范围 (0..65535) 的大约 1/4 未使用。

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

Assuming that the overflow is not a problem (JVM doing an automatic cast) is it better to do a bitshift instead of a cast?

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

I imagine the performance of the hashcode function vary significantly based on the complexity of the hashcode. Does the size of the prime multiplier not effect the performance?

不。无论大小、设置的位数等如何，在硬件中完成的操作都是相同的。这可能是几个时钟周期。它会因特定 CPU 的不同而有所不同，但无论输入值如何，它都应该是一个恒定时间操作。

Is it better/smarter/faster to use multiple primes in a custom hashcode function instead of a single multiplier? If not, is there some other advantage?

仅当它减少碰撞的可能性时，这取决于您使用的数字。如果您的哈希码取决于 A和 B并且它们在相同的范围内，您可以考虑使用不同的素数或移动输入值之一以减少位之间的重叠。由于您依赖于他们各自的哈希码，而不是直接依赖于他们的值，因此假设他们的哈希码提供良好的分布等是合理的。

您是否需要 (x, y) 的哈希码会想到的一个因素不同于 (y, x) .如果您的哈希函数处理 A和 B以同样的方式，然后 hash(x, y) = hash(y, x) .如果这就是您想要的，那么一定要使用相同的乘数。不是，使用不同的乘数是有意义的。

How about something like long lhash = prime * (hash1 ^ hash2); then using (int)((lhash >> 32) ^ lhash)? That's something I saw on another question here SO, but it wasn't really explained why it was a good idea to do it like that.

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

如果乘以一个数 n由素数 p ，以及最下面的 k n 的位都是零，那么最下面的 k产品位 n * p也将全为零。这很容易看出——如果你要乘以，比如 n = 0011 0000和 p = 0011 1011 ，那么乘积可以表示为两次移位操作的和。或者，

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

服用 p = 59并使用无符号 8 位整数和 16 位长整数，这里有一些例子。

 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)。

通过将高位与低位异或，输出的一致性会降低。更重要的是，根据这些信息来猜测输入值要困难得多。根据异或的工作原理，它可能意味着原始低位为 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)