Warum wird XOR oft in Java hashCode() verwendet, aber andere bitweise Operatoren werden selten verwendet?

Question

Ich sehe oft Code wie

int hashCode(){ 
    return a^b; 
} 

XOR Warum?

Answer 1

Von allen Bit-Operationen hat XOR die besten Bit-Shuffling-Eigenschaften.

Diese Wahrheitstabelle erklärt, warum:

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 

Wie Sie für AND und OR tun einen schlechten Job bei Misch Bits sehen können.

OR wird im Durchschnitt 3/4 Ein-Bits produzieren. UND auf der anderen Seite wird im Durchschnitt 3/4-Null-Bits erzeugen. Nur XOR hat eine geradzahlige Ein-Bit- oder Null-Bit-Verteilung. Das macht es für die Hash-Code-Generierung so wertvoll.

Denken Sie daran, dass Sie für einen Hash-Code möglichst viele Informationen des Schlüssels verwenden und eine gute Verteilung der Hash-Werte erhalten möchten. Wenn Sie AND oder OR verwenden, erhalten Sie Zahlen, die auf Zahlen mit vielen Nullen oder Zahlen mit vielen Einsen ausgerichtet sind.

Answer 2

XOR opertpr reversibel sind, also nehme ich an einen Bitstring als 0 0 1 und ich XOR es mit einem anderen Bitstring 1 1 1, die die Ausgabe

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

jetzt i xor die erste Saite mit dem Ergebnis Agan kann um die 2. Saite zu bekommen. d. h.

also, das macht die 2. Zeichenkette zu einem Schlüssel. Dieses Verhalten ist nicht mit anderen Bitoperator

Bitte lesen Sie diese für weitere Informationen gefunden ->Why is XOR used on Cryptography?

Answer 3

XOR hat folgende Vorteile:

• Es hängt nicht von der Reihenfolge der Berechnung dh a^b = b^a
• Es "verschwendet" keine Bits. Wenn Sie nur ein Bit in einer der Komponenten ändern, ändert sich der endgültige Wert.
• Es ist schnell, ein einziger Zyklus auf selbst die primitivsten Computer.
• Es bewahrt die gleichmäßige Verteilung. Wenn die zwei Teile, die du kombinierst, gleichmäßig verteilt sind, wird auch die Kombination sein. Mit anderen Worten, es neigt nicht dazu, den Bereich des Digests in ein schmaleres Band zu zerlegen.

Weitere Informationen here.

Answer 4

Es gibt einen weiteren Anwendungsfall: Objekte , in denen (einige) Felder verglichen werden müssen, ohne ihre Reihenfolge zu berücksichtigen. Zum Beispiel, wenn Sie ein Paar (a, b) immer gleich dem Paar sein wollen.
XOR hat die Eigenschaft a^b = b^a, so dass es in solchen Fällen in der Hash-Funktion verwendet werden kann.

Beispiele: (vollständige Code here)

Definition:

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 
} 

Nutzung:

 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}