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

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

int hashCode(){
  return a^b;
}

Почему XOR?

Ответ 1

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

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

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

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

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

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

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

Ответ 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}