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

Spesso vedo il codice come

int hashCode(){ return a^b; } 

Perché XOR?

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

Questa tabella di verità spiega perché:

 AB AND 0 0 0 0 1 0 1 0 0 1 1 1 AB OR 0 0 0 0 1 1 1 0 1 1 1 1 AB XOR 0 0 0 0 1 1 1 0 1 1 1 0 

Come puoi vedere per AND e OR fai uno scarso lavoro con i bit di missaggio.

OR produrrà in media 3/4 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.

Ricorda che per un codice hash si desidera utilizzare quante più informazioni possibili sulla 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.

XOR ha i seguenti vantaggi:

  • Non dipende dall’ordine di computazione, ad esempio a ^ b = b ^ a
  • Non “spreca” i bit. Se cambi anche solo un bit in uno dei componenti, il valore finale cambierà.
  • È veloce, un singolo ciclo anche sul computer più primitivo.
  • Conserva una distribuzione uniforms. Se i due pezzi che combini sono distribuiti in modo uniforms, così sarà la combinazione. In altre parole, non tende a comprimere l’intervallo del digest in una banda più stretta.

Maggiori informazioni qui .

XOR opertpr sono reversibili, cioè suppongo di avere una stringa di bit come 0 0 1 e I XOR con un’altra stringa di bit 1 1 1 , l’output è

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

ora posso eseguire x la prima stringa con il risultato per ottenere la seconda stringa. vale a dire

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

quindi, ciò rende la seconda stringa una chiave. Questo comportamento non è stato trovato con un altro operatore bit

Si prega di vedere questo per maggiori informazioni -> Perché XOR è usato su Cryptography?

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

Esempi: (codice completo qui )

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 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}