Почему XOR часто используется в java hashCode (), а другие побитовые операторы используются редко?

Question

Я часто вижу код вроде

int hashCode(){
  return a^b;
}

Почему XOR?

Answer 1

Из всех битовых операций XOR обладает лучшими свойствами перетасовки битов.

Эта таблица истинности объясняет, почему:

A B AND
0 0  0
0 1  0
1 0  0
1 1  1

A B OR
0 0  0
0 1  1
1 0  1
1 1  1

A B XOR
0 0  0
0 1  1
1 0  1
1 1  0

Как вы можете заметить, AND и OR плохо справляются с микшированием битов.

ИЛИ будет в среднем производить 3/4 однобитных. И, с другой стороны, будет выдавать в среднем 3/4 нулевых бита. Только XOR имеет четное однобитовое или нулевое распределение. Это делает его таким ценным для генерации хеш-кода.

Помните, что для хеш-кода вы хотите использовать как можно больше информации о ключе и получить хорошее распределение хеш-значений. Если вы используете AND или OR, вы получите числа, которые смещены в сторону либо чисел с множеством нулей, либо чисел с множеством единиц.

Answer 2

XOR имеет следующие преимущества:

• Это не зависит от порядка вычисления, то есть a ^ b = b ^ a
• Он не "тратит" биты. Если вы измените хотя бы один бит в одном из компонентов, окончательное значение изменится.
• Это быстро, один цикл даже на самом примитивном компьютере.
• Сохраняет равномерное распределение. Если две фигуры, которые вы объединяете, распределены равномерно, то и комбинация будет. Другими словами, он не стремится свести диапазон дайджеста в более узкую полосу.

Подробнее здесь .

Answer 3

Оператор XOR является обратимым, т. Е. Предположим, что у меня есть битовая строка как 0 0 1, и я XOR с другой битовой строкой 1 1 1, на выходе будет

0 xor 1 = 1
0     1 = 1
1     1 = 0

Теперь я могу снова переписать 1-ю строку с результатом, чтобы получить 2-ю строку. т.е.

0   1 = 1
0   1 = 1
1   0 = 1

Итак, вторая строка становится ключом. Это поведение не найдено с другим битовым оператором

Пожалуйста, смотрите это для получения дополнительной информации -> Почему XOR используется в криптографии?

Answer 4

Существует другой вариант использования: объекты , в которых (некоторые) поля должны сравниваться без учета их порядка . Например, если вы хотите, чтобы пара (a, b) всегда была равна паре (b, a).
XOR имеет свойство a ^ b = b ^ a, поэтому в таких случаях его можно использовать в хэш-функции.

Примеры: (полный код здесь )

Определение:

final class Connection {
    public final int A;
    public final int B;

    // some code omitted

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Connection that = (Connection) o;

        return (A == that.A && B == that.B || A == that.B && B == that.A);
    }

    @Override
    public int hashCode() {
        return A ^ B;
    }

    // some code omitted
}

использование:

        HashSet<Connection> s = new HashSet<>();
        s.add(new Connection(1, 3));
        s.add(new Connection(2, 3));
        s.add(new Connection(3, 2));
        s.add(new Connection(1, 3));
        s.add(new Connection(2, 1));

        s.remove(new Connection(1, 2));

        for (Connection x : s) {
            System.out.println(x);
        }

        // output:
        // Connection{A=2, B=3}
        // Connection{A=1, B=3}