当重写hashCode()方法时，使用更大的质数作为乘数

Question

当重写hashCode()方法时，使用更大的质数作为乘数

13

我最近花了几个小时阅读哈希函数的相关知识，并积累了一些有关在自定义哈希函数实现中使用质数作为乘数的问题。以下是我想请教的问题：

在这里@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);
}

如果prime是一个大数，那么这是否会导致返回的 int 溢出?

假设溢出不是问题（JVM 自动进行强制转换），使用位移比强制转换更好吗？
我想象哈希函数的性能会根据其复杂性而有所不同。使用的质数乘法器的大小不影响性能吗？
在自定义哈希码函数中使用多个质数而不是单个乘数是否更好/更聪明/更快？如果不是，是否有其他优点？参见下面的示例，该示例来自@jinguy对相关问题的回答：

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)。我在Stack Overflow上看到过这样的代码，但没有详细解释为什么这种做法是好的。

- posdef

最好分别发布多个问题，而不是像上面那样分组在一起。这样更容易回答，而且重点问题更有可能对未来的谷歌搜索有用。顺便说一句，感谢您在研究中引用参考资料。 - GargantuChet

2

@GargantuChet 虽然我通常会同意你的说法，但我认为这4个问题实际上非常相关。为主题的每个细节提出一个新问题最终将导致问题过多，我认为。（不过看看版主们怎么想会很酷） - posdef

2个回答

4

溢出不是问题。哈希值本来就受到狭窄的值集的限制。
你发布的第一个哈希函数并不是很好。在大多数情况下，使用 return (prime * hash1) ^ hash2; 可以减少碰撞的数量。
乘以单个字长度的整数通常非常快，而乘以不同数字之间的差异微不足道。此外，执行时间被函数中其他一切内容所压倒。
对于每个部分使用不同的质数乘法因子可能会降低碰撞的风险。

- Antimony

1

@posdef 这是不可能被证明的，因为总会存在一些病态案例使其不成立。 - Peter Lawrey

2

考虑到人类的参与，你可以说病态情况会比你预期的更加频繁发生。 - Peter Lawrey

1

@PeterLawrey 感谢你让我笑了; 在办公室加班时，很少有机会突然冒出一个微笑。 :) - posdef

1

一个例子，String.hashCode()会在提供其之前未计算过的情况下计算hashCode。也就是说，如果hashCode为0，则计算hashCode。但是如果hashCode为0，它将重复计算。空字符串为0，其他任何字符串为0的概率是40亿分之一。但是，如果您是黑客，可以构造各种具有hashCode 0的字符串，这可以帮助您进行DOS攻击。其中一些看起来像普通单词。https://dev59.com/b3E95IYBdhLWcg3wb9db - Peter Lawrey

1

@Antimony：一些有用的属性是相似的，但在那些两个值匹配的情况比不匹配的情况更常见时，加法要好得多。对于所有int值计算X+X将产生一个碰撞。对于所有int值计算X^X将为每个值产生4,294,967,295个碰撞。 - supercat

显示剩余5条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- GargantuChet · Accepted Answer

先提前道歉，内容较长。欢迎提出建议或直接编辑。--Chet

发生了溢出，但不是异常。

危险并非来自失去准确性，而是失去范围。让我们举一个荒谬的例子，其中“prime”是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的人不太可能关心多个移位和加法操作可以合并为单个整数乘法的情况。

我想hashcode函数的性能会根据hashcode的复杂性而显著变化。质数乘积的大小是否不影响性能？

不是。无论大小，设置的位数等，在硬件上执行的操作都是相同的。这可能需要几个时钟周期。它将根据特定的CPU而异，但是不管输入值如何，应该是一个恒定时间的操作。

在自定义hashcode函数中使用多个质数而不是单个乘数会更好/更明智/更快吗？如果没有，还有其他好处吗？

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

有一些因素需要考虑，例如您是否希望<（x，y）>和<（y，x）>的哈希代码不同。如果您的哈希函数以相同方式处理A和B，则hash（x，y）= hash（y，x）。如果这正是您想要的，请务必使用相同的乘数。否则，使用不同的乘数是有意义的。

像long lhash = prime *（hash1 ^ hash2）;然后使用（int）（（lhash >> 32）^ lhash）如何？这是我在SO上看到的另一个问题，但是没有真正解释为什么这样做是一个好主意。

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

如果将一个数字n乘以一个质数p，并且n的最低k位都是零，则乘积n * p的最低k位也将全部为零。这很容易理解 - 如果你正在计算，比如说，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)