覆盖hashCode（）时，使用较大的质数作为乘数

Question

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

• 在对@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);
    }

int如果prime数量很大，这是否会导致返回的溢出？

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

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

• 在自定义哈希码函数中使用多个素数而不是一个乘法器会更好/更智能/更快吗？如果没有，还有其他优势吗？请参见@jinguy对相关问题的回答中的以下示例：

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

  }

aan 在哪里int，b是a String和cis boolean。

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

Answer 1

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

有溢出，但并非例外。

危险不是来自失去准确性，而是失去范围。让我们使用一个荒谬的示例，其中“素数”是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)值中的位数来设置由偶数乘数转换为保证无用的最低有效位数。

现在，让我们考虑一个值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到处都是地图。如果(hash1 ^ hash2)低至8，它就会溢出。即使对于很小的输入数字，它也会使用所有16​​位。即使输入数字在相对较小的范围内，哈希值在整个范围内的聚类也要少得多。

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

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

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

否。在硬件中进行的操作相同，而与大小，设置的位数等无关，这可能是几个时钟周期。它会因特定的CPU而异，但无论输入值如何，都应为恒定时间操作。

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

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

一个要考虑的因素就是您是否希望哈希码(x, y)不同于(y, x)。如果您的哈希函数对待A，并B以同样的方式，然后hash(x, y) = hash(y, x)。如果那是您想要的，则务必使用相同的乘数。并非如此，使用其他乘数将是有意义的。

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

有趣的问题。在Java中，long是64位，而ints是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)

通过仅丢弃结果的高位，当非素被乘数的低位都为零时，结果哈希值的范围将受到限制。在特定上下文中这是否是一个问题，具体取决于上下文。但是对于一般的哈希函数，即使输入数字中包含模式，也应避免限制输出值的范围。在安全性应用程序中，避免发生任何可能使某人基于输出中的模式推断原始值的事情就显得尤为关键。仅取低位即可显示某些原始位的确切值。如果我们假设该操作涉及将输入数字与大质数相乘，那么我们知道原始数的右侧与散列输出具有一样多的零（因为质数’

通过对高位与低位进行异或运算，输出的一致性会降低。更重要的是，根据此信息来猜测输入值要困难得多。根据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)