Perché XOR viene spesso utilizzato in java hashCode() ma altri operatori bit a bit vengono usati raramente?

Question

Vedo spesso il codice come

int hashCode(){ 
    return a^b; 
} 

Perché XOR?

Answer 1

Di tutte le operazioni di bit XOR ha le migliori proprietà di shuffling dei bit.

Questa verità-tabella spiega perché:

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 

Come si può vedere di AND e OR fare un lavoro poveri a bit di miscelazione.

OR produrrà in media 3/4 di un bit. E d'altra parte produrrà in media 3/4 null-bit. Solo XOR ha una distribuzione anche un bit contro un bit nullo. Ciò lo rende così prezioso per la generazione di codice hash.

Ricordare che per un codice hash si desidera utilizzare quante più informazioni possibili della chiave e ottenere una buona distribuzione dei valori hash. Se usi AND o OR otterrai numeri che sono prevenuti verso entrambi i numeri con molti zeri o numeri con molti di quelli.

Answer 2

XOR opertpr sono reversibili, cioè supponiamo di avere una stringa di bit come 0 0 1 e XOR con un'altra stringa di bit 1 1 1, l'uscita è

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

ora posso AGAN xor la 1a corda con il risultato per ottenere la seconda corda. Ad esempio

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

quindi, che rende la seconda stringa una chiave. Questo comportamento non è stato trovato con operatore altro po

Si prega di vedere questo per ulteriori informazioni ->Why is XOR used on Cryptography?

Answer 3

XOR presenta i seguenti vantaggi:

• non dipende in ordine di calcolo vale a dire un^b = b^a
• Non "spreca" i bit. Se cambi anche solo un bit in uno dei componenti, il valore finale cambierà.
• È rapido, un singolo ciclo anche sul computer più primitivo.
• Conserva una distribuzione uniforme. Se i due pezzi che combini sono distribuiti in modo uniforme, così sarà la combinazione. In altre parole, non tende a comprimere l'intervallo del digest in una banda più stretta.

Ulteriori informazioni here.

Answer 4

C'è un altro caso d'uso: oggetti in cui (alcuni) campi devono essere confrontati senza riguardo al loro ordine. Ad esempio, se si desidera una coppia (a, b) essere sempre uguale alla coppia (b, a).
XOR ha la proprietà che a^b = b^a, quindi può essere utilizzato in funzione hash in questi casi.

Esempi: (codice completo here)

definizione:

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 
} 

utilizzo:

 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}