Why we use 31 in hashCode() method?

Question

我们用 eclipse 自动生成 hashCode（） 方法时一般会得到类似如下的代码：
...
final int PRIME = 31;
int result = 1;
result = PRIME * result + a;
result = PRIME * result + ((b == null) ? 0 : b.hashCode());
result = PRIME * result + Float.floatToIntBits(c);
...
我的疑问是这里的 31 是如何得来的？为什么下面每步都要将上面的结果乘以 31 再加？这个算法如何得来？

Answer 1

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

Answer 2

In fact, I have seen this description before, but I don't think it answers my question. I mean why multiplication is needed here? What's wrong if implementing like below:
result = result + a;
result = result + ((b == null) ? 0 : b.hashCode());
result = result + Float.floatToIntBits(c);

Answer 3

exactly!    public static void main(String... args) throws Exception {   
        String[] names = {"332", "a7"};   
        for (String s : names)   
            System.out.println(hash(s) + ":\t" + s);   
    }   
    
    private static int hash(String s) {   
        int h = 0;   
        int len = s.length();   
        for (int i = 0; i < len; i++)   
            h = 31 * h + s.charAt(i);   
        return h;   
    }  gives output: 50642: 332
3062: a7
But if we replace 31 with 1, we get:
152: 332
152: a7

Answer 4

其实说起这个问题就要说起Hash相关的特殊数据结构如hashMap,hashSet,对于这些结构最害怕的事情就是hashCode碰撞(hash冲突).举一个极端的例子,你写一个类Test,覆盖它的hashCode()都返回一个常量,你把Test的N个实例存到一个基于Hash算法的结构中如HashSet,你会发现其存储方式和List一样.此时HashSet完全失去了它的速度优势.
因此,如何在生成HashCode时尽量防止碰撞是很重要的.在这个基础上通过测试以及部分理论证明,发现使用一个质数作为生成HashCode的因子时,往往能够得到分布相对均匀的映射区间.从而尽可能的避免在某一个数值区间内发生大量的碰撞.
至于为什么选31,因为这是一个经验值,这样可以获取效率与空间的相对优值.(实际上计算hashcode的方法很多,使用31只能说是一个经典值而已,相当多的语言都不这样算的.)我知道的就这么多了,也是以前在研究HashMap时查资料看到的.其实你可以上网搜搜,其实你问的也是经典问题了,可以说是有定论的.

Answer 5

谢谢 coldanimal 和 orangemike