什么是哈希码计算的明智素数?

2022-08-31 14:35:22

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的历史,而是关于使用相同的基本模板在新代码中什么会更好。那里的答案都没有试图回答这个问题。


答案 1

我建议使用92821。原因如下。

要对此给出有意义的答案,您必须了解 和 的可能值。总的来说,我唯一能想到的是,在许多情况下,小值比大值更常见。(15 在程序中作为值出现的几率比438281923要好得多。因此,通过选择合适的素数来使最小的哈希码冲突尽可能大似乎是一个好主意。对于31来说,这相当糟糕 - 已经为,并且您具有与 和 相同的哈希值。iji=-1j=31i=0j=0

由于这很有趣,我写了一个小程序,在这个意义上搜索整个int范围的最佳素数。也就是说,对于每个素数,我搜索了所有值的最小值,这些值具有与 相同的哈希码,然后取该最小值尽可能大的素数。Math.abs(i) + Math.abs(j)i,j0,0

鼓点:从这个意义上说,最好的素数是486187739(最小的碰撞是)。几乎同样好,更容易记住的是92821,最小的碰撞是 。i=-25486, j=67194i=-46272 and j=46016

如果你给“小”另一种含义,并希望成为尽可能大的碰撞的最小值,结果会有所不同:最好的是1322837333,但我最喜欢的92821(最小的碰撞)再次几乎与最佳值一样好。Math.sqrt(i*i+j*j)i=-6815 and j=70091-46272,46016

我确实承认,这些计算在实践中是否有多大意义是相当值得商榷的。但我确实认为,将92821作为素数比31更有意义,除非你有充分的理由不这样做。


答案 2

实际上,如果你取一个如此之大的素数,以至于它接近 ,你也会因为模算术而遇到同样的问题。如果你希望对长度为2的字符串进行哈希处理,也许最接近平方根的素数是最好的,如果你哈希的字符串更长,那也没关系,无论如何,碰撞都是不可避免的......INT_MAXINT_MAX