乘法应该是次优的。为什么在 hashCode 中使用它？

Question

哈希函数非常有用且用途广泛。通常，它们用于将一个空间映射到一个更小的空间。当然，这意味着两个对象可能会散列到相同的值（碰撞），但这是因为您正在减少空间（鸽笼原理）。函数的效率很大程度上取决于哈希空间的大小。

令人惊讶的是，许多 Java hashCode 函数正在使用乘法来生成新对象的哈希码，如下所示（create-a-hashcode-method-java）

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((email == null) ? 0 : email.hashCode());
    result = prime * result + (int) (id ^ (id >>> 32));
    result = prime * result + ((name == null) ? 0 : name.hashCode());
    return result;
}

如果我们想在同一范围内混合两个哈希码，xor 应该比加法好得多，我认为传统上是这样使用的。如果我们想增加空间，移动一些字节然后异或仍然是有意义的。我想乘以 31 几乎与将一个哈希值移动 1 然后添加相同，但它的效率应该低得多......

虽然这是推荐的方法，但我想我错过了一些东西。所以我的问题是为什么会这样？

笔记：

• 我不是问为什么我们使用质数。很明显，如果我们使用乘法，我们应该使用素数。然而，乘以任何数字，即使是素数，仍然不是 xor 的最佳选择。这就是为什么例如所有这些其他非加密哈希函数- 以及大多数加密 - 使用异或而不是乘法......
• 我确实没有任何迹象（除了所有那些众所周知的哈希函数）xor 会更好。事实上，仅仅因为它被广泛接受，我怀疑乘以一个素数和总和应该同样好，而且在实践中更好。我问这是为什么...
• intJava 中的类型可用于表示从 -2147483648 到 2147483647 的任何整数。
• 有时一个对象的哈希码可能是它的内存地址（这在很多情况下是有意义的并且是有效的）（如果从例如 object 继承）

Answer 1

对此的答案是多种因素的混合：

• 在现代体系结构中，执行乘法与移位所花费的时间可能无法在给定的指令流水线中总体上进行测量——它更多地与 CPU 上相关执行单元的可用性有关，而不是“原始”花的时间;
• 在实践中，在日常编程中与标准集合库集成时，哈希函数的正确性、“足够好”和易于在 IDE 中实现自动化通常比使其尽可能完美更重要；
• 集合库通常会在幕后添加二级散列函数和潜在的其他技术，以克服散列函数本来会很差的一些弱点；
• 使用可调整大小的集合，有效的散列函数的目标是将其散列分布在任意大小的散列表的可用范围内（尽管正如我所说，它将从内置的辅助函数中获得帮助）：乘以“魔术”常量通常是实现这一目标的廉价方法（或者，即使乘法结果比移位更昂贵：考虑到好处，仍然足够便宜）；加法而不是异或可能有助于轻微地允许这种“雪崩”效应。（在大多数实际情况下，您可能会发现它们同样有效。）
• 您通常可以假设 JIT 编译器“知道”等价物，例如移动 5 个位置和减去 1 而不是乘以 31。仅仅因为您在源代码中写入“*31”并不意味着它会被编译为字面上的乘法指令。（但实际上，它可能是这样，因为不管您怎么想，乘法指令在所讨论的体系结构上平均来说很可能“更快”......通常最好让您的代码坚持所需的逻辑并让在这种情况下，JIT 编译器会处理低级优化。）