Warum sind oft XOR in Java hashCode () verwendet aber eine andere Bit-Operatoren sind selten verwendet?

Question

Ich sehe Code oft wie

int hashCode(){
  return a^b;
}

Warum XOR?

Answer 1

Von allen Bit-Operationen XOR hat die besten Bit schlurfenden 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.

oder werden im Durchschnitt produzieren 3/4 ein Bit. Und auf der anderen Seite wird im Durchschnitt 3/4 Null-Bits erzeugen. Nur hat XOR noch ein Bit gegen Null-Bit-Verteilung. Das macht es so wertvoll für die Hash-Code-Generierung.

Beachten Sie, dass für einen Hash-Code, den Sie so viele Informationen des Schlüssels wie möglich nutzen wollen und eine gute Verteilung der Hash-Werte erhalten. Wenn Sie AND oder OR Sie Zahlen erhalten, die entweder in Richtung Zahlen mit vielen Nullen oder Zahlen mit vielen Einsen vorgespannt ist.

Answer 2

XOR hat folgende Vorteile:

• Es hängt nicht von der Reihenfolge der Berechnung d a ^ b = b ^ a
• Es ist nicht "Abfall" Bits. Wenn Sie auch nur ein Bit in einer der Komponenten ändern, wird der Endwert ändern.
• Es ist schnell, ein einzelner Zyklus auf selbst die primitivsten Computer.
• Es bewahrt eine gleichmäßige Verteilung. Wenn die beiden Stücke, die Sie kombinieren gleichmäßig verteilt sind, werden so die Kombination sein. Mit anderen Worten, neigen sie nicht die Reichweite der verdauen in ein engeres Band kollabieren.

Weitere Informationen hier .

Answer 3

XOR-Operator ist reversibel, das heißt Angenommen, ich habe einen Bitstring als 0 0 1 und I XOR es mit einem anderen Bitstring 1 1 1, die die Ausgabe ist

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

Jetzt kann ich wieder xor der 1. Saite mit dem Ergebnis der zweiten Zeichenfolge zu erhalten. d.

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

So, das macht die zweite Zeichenfolge einen Schlüssel. Dieses Verhalten wird nicht mit anderem Bitoperator

gefunden

Bitte für weitere Informationen siehe -> Warum ist XOR auf Kryptographie verwendet

Answer 4

Es ist ein weiterer Anwendungsfall: Objekte , in dem (etwas) Felder müssen ohne Bezug auf ihre verglichen werden, . Zum Beispiel, wenn Sie ein Paar (a, b) wollen immer gleich mit dem Paar (b, a).
XOR hat die Eigenschaft, dass a ^ b = b ^ a, so dass es in Hash-Funktion in solchen Fällen verwendet werden kann.

Beispiele: (vollständiger Code hier )

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}