为什么java hashcode实现31 * x + y比x + y更好？

Question

我对关于哪种哈希码实现更好的java面试问题感到困惑。我们有课

Point {int x, y; }

。为什么这个类的 hashcode

31 * x + y

的实现比

x + y

更好？正确的答案是“乘法器创建了哈希码值对处理字段顺序的依赖，这最终产生了更好的哈希函数”。但我不明白为什么处理顺序是这里的重点，因为当我执行

31 * x + y

时，整个表达式

point1.equals(point2);

正在计算，而且无论它以什么顺序发生。难道我错了？

Answer 1

如果使用

x+y

那么如何区分点(3,4)和(4,3)呢？两者将具有相同的哈希码...

现在虽然

31 * x + y

不会很完美，但在同样的情况下，会好很多。

注意：根据哈希的定义，不存在完美的哈希。唯一的事情就是分析给定的哈希函数会发生什么样的冲突。在几何情况下，第一个引入了非常简单且常见的对称性的碰撞。因此，在非常常见的情况下，可能会发生太多冲突。

Answer 2

假设您有两个字符串属性

prop1

和

prop2

，以及两个对象：

A: {prop1="foo", prop2="bar"}
B: {prop1="bar", prop2="foo"}

这些是明显不同的值，设置哈希码来区分它们很有用。如果您只需将属性的哈希码相加，您将获得

A

和

B

相同的值。相反，通过乘法和加法，哈希码将根据属性序列而不同。

您似乎可能稍微误解了该建议：乘法和加法的目的是创建对对象内属性的语义顺序的依赖，而不是计算的执行顺序。

Answer 3

Jean-Baptiste Yunès 的答案是正确的，但我将添加以下示例来说明（请记住，它是用 javascript 编写的，只是因为我快速实现了该示例）：

class Point {
    constructor(x, y) {
        this.x = x;
        this.y = y;
    }
}

function getHashCollisions(collection, hashFunction) {
    const collisionMap = new Map();
    let count = 1;
    let total = collection.length;
    for (const point of collection) {
        console.log(`calculating ${count++}/${total}`);
        const currentHash = hashFunction(point);
        const hashCount = collisionMap.has(currentHash) ? collisionMap.get(currentHash) +1 : 1;
        collisionMap.set(currentHash, hashCount);
    }
    return collisionMap;
}

function generateDataset(rangeX, rangeY) {
    const points = [];
    let count = 1;
    for (let x = 0; x < rangeX; x++) {
        for (let y = 0; y < rangeY; y++) {
            console.log(`generating ${count++} Point(${x};${y})`);
            points.push(new Point(x, y));
        }
    }
    return points;
}

function calculateAndGenerateReport(dataset, hashFunction, hashFunctionName) {
    const hashes = getHashCollisions(dataset, hashFunction);
    const totalCollisions = Array.from(hashes.values()).filter(currentCollisionCount => currentCollisionCount > 1).length;
    const highestCollisionCount = Array.from(hashes.values()).reduce((currentHighest, current) => current > currentHighest ? current : currentHighest) - 1;
    return `${hashFunctionName}: ${totalCollisions} collisions, highest collision count: ${highestCollisionCount}`;
}

const dataset = generateDataset(100, 100);

const literalHashesReport = calculateAndGenerateReport(dataset, point => point.x + point.y, "literal hash function:");
const onePrimeHashesReport = calculateAndGenerateReport(dataset, point => 31 * point.x + point.y, "one prime multiplication hash function:");
const twoPrimesHashesReport = calculateAndGenerateReport(dataset, point => 31 * point.x + 37 * point.y, "two primes multiplication hash function:");
const twoLargePrimesHashesReport = calculateAndGenerateReport(dataset, point => 8191 * point.x + 131071 * point.y, "two large primes multiplication hash function:");

console.log(literalHashesReport);
console.log(onePrimeHashesReport);
console.log(twoPrimesHashesReport);
console.log(twoLargePrimesHashesReport)

结果：

literal hash function: 197 collisions, highest collision count: 99
one prime multiplication hash function: 3107 collisions, highest collision count: 3
two primes multiplication hash function: 3359 collisions, highest collision count: 2
two large primes multiplication hash function: 0 collisions, highest collision count: 0

这表明我们选择“计算”哈希值的（素数）数字大大降低了冲突的概率。