Por que o XOR é frequentemente usado no Java Hashcode (), mas outros operadores bit -bit são usados ​​raramente?

Question

Muitas vezes vejo código como

int hashCode(){
  return a^b;
}

Por que xor?

Answer 1

De todas as operações de bits, o XOR tem as melhores propriedades de embaralhamento.

Esta mesa de verdade explica o porquê:

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

Como você pode ver e / ou fazer um mau trabalho em misturar bits.

Ou produzirá em média 3/4 de uma parte. E, por outro lado, produzirá em média 3/4 bits nulos. Somente o XOR possui uma distribuição uniforme de um bit vs. null-bit. Isso o torna tão valioso para a geração de código de hash.

Lembre-se de que, para um código de hash, você deseja usar o máximo de informações possível da chave e obtenha uma boa distribuição de valores de hash. Se você usa e / ou obterá números tendenciosos em direção a números com muitos zeros ou números com muitos.

Answer 2

XOR tem as seguintes vantagens:

• Não depende da ordem de computação, ou seja, a^b = b^a
• Não "desperdiça" pedaços. Se você mudar um pouco em um dos componentes, o valor final mudará.
• É rápido, um único ciclo, mesmo no computador mais primitivo.
• Preserva a distribuição uniforme. Se as duas peças que você combinar forem distribuídas uniformemente, a combinação será. Em outras palavras, ele não tende a desmoronar o alcance do digerido em uma banda mais estreita.

Mais informações aqui.

Answer 3

O operador XOR é reversível, ou seja, suponha que eu tenha um pouco de corda como 0 0 1 E eu xori com outra corda de bit 1 1 1, a saída é

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

Agora posso novamente xorar a 1ª string com o resultado para obter a segunda string. ou seja

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

Então, isso faz da segunda sequência uma chave. Este comportamento não é encontrado com outro operador de bits

Por favor, veja isso para mais informações -> Por que o XOR é usado na criptografia?

Answer 4

Há outro caso de uso: objetos em que (alguns) campos devem ser comparados sem a ordem deles. Por exemplo, se você quiser um par (a, b) Seja sempre igual ao par (b, a).
XOR tem a propriedade que a ^ b = b ^ a, para que possa ser usado na função de hash nesses casos.

Exemplos: (código completo aqui)

definição:

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
}

uso:

        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}