什么是哈希码计算的明智素数?
Eclipse 3.5有一个非常好的特性来生成Java hashCode()函数。例如,它会生成(略微缩短:)
class HashTest {
int i;
int j;
public int hashCode() {
final int prime = 31;
int result = prime + i;
result = prime * result + j;
return result;
}
}
(如果类中有多个属性,则对每个附加属性重复。对于 ints ,可以省略 .hashCode()。result = prime * result + attribute.hashCode();
这似乎很好,但对于选择31的素数。它可能取自Java String的hashCode实现,该实现是出于性能原因而使用的,这些原因在引入硬件乘法器后早已消失。在这里,i 和 j 的小值有许多哈希码冲突:例如 (0,0) 和 (-1,31) 具有相同的值。我认为这是一件坏事(TM),因为小值经常出现。对于String.hashCode,您还可以找到许多具有相同哈希码的短字符串,例如“Ca”和“DB”。如果你取一个大的素数,如果你选择正确的素数,这个问题就会消失。
所以我的问题是:什么是好的素数选择?你用什么标准来找到它?
这是一个一般性的问题 - 所以我不想给i和j一个范围。但我认为在大多数应用程序中,相对较小的值比大值更频繁地出现。(如果你有大的值,素数的选择可能并不重要。它可能不会有太大的区别,但更好的选择是改善这一点的简单而明显的方法 - 那么为什么不这样做呢?Commons lang HashCodeBuilder还建议了奇怪的小值。
(澄清:这不是为什么字符串中的Java的hashCode()使用31作为乘数的副本?因为我的问题不涉及JDK中31的历史,而是关于使用相同的基本模板在新代码中什么会更好。那里的答案都没有试图回答这个问题。