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

Question

Hash Functions 非常有用且用途广泛。通常，它们用于将 space 映射到更小的 space。当然这意味着两个对象可能散列为相同的值（碰撞），但这是因为您正在减少 space (pigeonhole principle)。函数的效率很大程度上取决于散列的大小 space.

令人惊讶的是，许多 Java hashCode 函数都使用乘法来生成新对象的哈希码，例如遵循 (creating-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 应该比加法好得多，我认为这是传统上使用的。如果我们想增加 space，移动一些字节然后异或运算仍然是有意义的。我想乘以 31 几乎与将一个哈希值移动 1 然后相加是一样的，但它的效率应该低得多...

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

备注：

我不是在问 why we use a prime. It is pretty clear that if we used multiplication, we should go with a prime. However multiplying by any number, even a prime, should still be suboptimal to xor. That is why e.g. all these other non-cryptographic hash functions - 以及大多数密码 - 使用 xor 而不是乘法...
我确实没有迹象表明（除了所有那些众所周知的散列函数）xor 会更好。事实上，正是因为它被广泛接受，我怀疑乘以素数和和应该同样好，而且在实践中更好。我在问为什么这是...
Java中的int类型可以用来表示从-2147483648到2147483647之间的任意整数。
有时一个对象的哈希码可能是它的内存地址（这在很多情况下都有意义并且很有效）(if inherited from e.g. object)

Answer 1

这个问题的答案是多种因素的结合：

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

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

Multiplication should be suboptimal. Why is it used in hashCode?

java

hash

hashcode