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

Question

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

@Override
html" target="_blank">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会更好。事实上，仅凭它被如此广泛地接受，我怀疑它应该是好的，并且在实践中更好的乘以一个素数和和。我在问为什么这是...
• Java中的int类型可用于表示从-2147483648到2147483647之间的任何整数。
• 有时对象的hashcode可能是它的内存地址（这在很多情况下很有意义并且很有效）（如果从例如对象继承）

Answer 1

对此的答案是不同因素的混合：

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