Почему java реализация хэш-кода 31 * x + y лучше, чем x + y?

Question

Я запутался с java вопросом о том, какая реализация хэш-кода лучше. У нас есть класс Point {int x, y; }. Почему реализация хэш-кода 31 * x + y для этого класса лучше, чем x + y? Правильный ответ: «Множитель создает зависимость значения хеш-кода от порядка обработки полей, что в конечном итоге приводит к улучшению функции ha sh». Но я не могу понять, почему порядок обработки здесь имеет смысл, потому что все выражение 31 * x + y вычисляется, когда я выполняю point1.equals (point2); И не важно, в каком порядке это происходит. Я не прав?

Answer 1

Если вы используете x+y, то как различить guish баллов (3,4) и (4,3)? Оба будут иметь одинаковый хэш-код ...

Теперь, хотя 31 * x + y не будет идеальным, в том же случае это будет намного лучше.

Примечание: по определению хэширования нет идеального хеширования. Единственное, что нужно проанализировать, какие коллизии происходят для данной функции ha sh. В геометрическом случае первый вводит столкновения для очень простого и обычного свойства симметрии. Таким образом, в очень распространенных случаях может быть слишком много столкновений.

Answer 2

Представьте, что у вас есть два строковых свойства prop1 и prop2 и два объекта:

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

Это явно разные значения, и полезно установить код ha sh для различения guish между ними. Если вы просто добавите коды свойств ha sh вместе, вы получите одинаковое значение для A и B. Вместо этого, путем умножения и сложения код ha sh будет отличаться в зависимости от последовательности свойств.

Возможно, вы слегка ошибочно интерпретируете совет: цель умножения-и-сложения - создать зависимость от порядка семанти c свойств внутри объекта , а не порядка выполнения вычисления .

Answer 3

Ответ Жан-Батиста Юнеса является правильным, но я добавлю следующий пример, чтобы проиллюстрировать (имейте в виду, что он в 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

Это показывает, что (простые) числа, которые мы выбираем для "вычисления" га sh, значительно уменьшают вероятность столкновений.