java - 为什么Eclipse生成的hashCode()方法返回的哈希码不是很好？

Question

我通常让 Eclipse 为我生成 hashCode() 方法，但现在我发现生成的哈希码可能不是很好的迹象。

在哈希集中使用由 Eclipse 生成的 hashCode() 方法返回的哈希码导致查找速度比使用手动编码的 hashCode() 方法慢大约 6 倍。

这是我的测试:

• 具有三个 int 字段的类。
• hashCode() 和 equals() 方法已由 Eclipse 生成。
• 用该类的 1.000.000 个实例填充 HashSet。
• 在HashSet中查找每个实例
• 重复查找 10 次。

代码:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class MyPojo {

    private final int a;
    private final int b;
    private final int c;

    public MyPojo(int a, int b, int c) {
        super();
        this.a = a;
        this.b = b;
        this.c = c;
    }

    public static void main(String[] args) {

        List<MyPojo> listOfPojos = new ArrayList<MyPojo>();
        Set<MyPojo> setOfPojos = new HashSet<MyPojo>();

        for (int countA = 0; countA < 100; countA++) {
            for (int countB = 0; countB < 100; countB++) {
                for (int countC = 0; countC < 100; countC++) {
                    MyPojo myPojo = new MyPojo(countA, countB, countC);
                    listOfPojos.add(myPojo);
                    setOfPojos.add(myPojo);
                }
            }
        }

        long startTime = System.currentTimeMillis();

        for (int count = 0; count < 10; count++) {
            for (MyPojo myPojo : listOfPojos) {
                if (!setOfPojos.contains(myPojo)) {
                    throw new RuntimeException();
                }
            }
        }

        long endTime = System.currentTimeMillis();
        System.out.format("Execution time: %3f s", (endTime - startTime) / 1000.0);

    }

    // Generated by Eclipse
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + a;
        result = prime * result + b;
        result = prime * result + c;
        return result;
    }

    // Generated by Eclipse
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        MyPojo other = (MyPojo) obj;
        if (a != other.a)
            return false;
        if (b != other.b)
            return false;
        if (c != other.c)
            return false;
        return true;
    }

}

在我的机器上，这导致执行时间约为 1.23 秒。

现在用我在别处找到的这个方法替换 hashCode() 方法:

@Override
public int hashCode() {
    final int magic = 0x9e3779b9;
    int seed = 0;
    seed ^= this.a + magic + (seed << 6) + (seed >> 2);
    seed ^= this.b + magic + (seed << 6) + (seed >> 2);
    seed ^= this.c + magic + (seed << 6) + (seed >> 2);
    return seed;
}

现在执行时间只有0.2秒，快了大约6倍!

为什么？

---

编辑:

按照建议，计算哈希值“重新出现”的次数可得出以下结果:

使用 Eclipse 生成的 hashCode() 方法:

1: 62
2: 62
3: 1406
4: 440
5: 62
6: 1406
7: 62
8: 440
9: 52094
10: 4670
11: 4670
12: 26144
13: 1358
14: 1358
15: 1358
16: 2716

用手工编码的 hashCode() 方法:

1: 79093
2: 180316
3: 23444
4: 107020
5: 2213
6: 6821
7: 296
8: 960
10: 12

所以Eclipse生成的方法只给出了62个只出现过一次的哈希码。

手写版本给出了 79093 个哈希码只出现了一次，180316 个哈希码只出现了两次。

差异很大。

---

编辑 2:

还尝试了 Objects.hash(...)，与 Eclipse 生成的 hashCode() 方法相比，这给出了相同的“重新出现”计数。

@Override
public int hashCode() {
    return Objects.hash(a, b, c);
}

此外，这实际上进一步减慢了执行速度:1.38 秒

---

编辑 3:

这里解释了上面更好的哈希码方法中的“魔数(Magic Number)”从何而来:

Magic number in boost::hash_combine

---

编辑 4:使用 http://projectlombok.org生成 hashCode() 和 equals() 方法

Lombok 给出了最好的结果:

1: 33958
2: 146124
3: 8118
4: 162360

Execution time: 0.187000 s

Answer 1

Eclipse hashCode() 遵循 Effective Java 中建议的指南。作者说这个方法还算不错，但绝对不是最好的。

如果hashCode 性能不理想，您可以自由寻找替代方案。

还有一件事我想提及的是，对于几乎每个 hashCode 函数，您都可以找到一些数据集来阻止函数均匀分布哈希值，从而使您代码中的 HashSet 就像一个长列表。

您可以在此处查看其他讨论:Is the hashCode function generated by Eclipse any good?

您可能还想阅读 this