Warum sind XOR oft in java hashCode() aber ein anderer bitweisen Operatoren werden nur selten verwendet?

Sehe ich oft code wie

int hashCode(){
  return a^b;
}

Warum XOR?

InformationsquelleAutor Andrei N | 2010-02-25
  1. 88

    Alle bit-Operationen XOR hat den besten bit-mischen Eigenschaften.

    Diese Wahrheit-Tabelle 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 man sehen kann, für UND und ODER machen einen schlechten job bei Misch-bits.

    ODER wird im Durchschnitt produzieren eine 3/4-bits. UND auf der anderen Seite produzieren im Durchschnitt 3/4 null-bits. Nur XOR hat selbst ein-bit-vs. null-bit-Verteilung. Das macht es so wertvoll für die hash-code-Generierung.

    Daran erinnern, dass für einen hash-code, den Sie verwenden möchten, wie viel Informationen der Schlüssel wie möglich zu erhalten und eine gute Verteilung der hash-Werte. Wenn Sie mit UND oder ODER du wirst zahlen, die sind voreingenommen gegenüber entweder zahlen mit vielen Nullen oder zahlen mit vielen Einsen.

    • +1 Das ist sehr informativ.....
    InformationsquelleAutor Nils Pipenbrinck
  2. 19

    XOR hat die folgenden Vorteile:

    • Es hängt nicht von der Reihenfolge der Berechnung, d.h. a^b = b^a
    • Es nicht "überflüssige" bits. Wenn Sie auch nur ein bit in einer der Komponenten, der Letzte Wert, der geändert wird.
    • Es ist schnell, einen einzigen Zyklus auf, selbst die primitivsten computer.
    • Es bewahrt die gleichmäßige Verteilung. Wenn die beiden Stücke, die Sie kombinieren sind gleichmäßig verteilt werden, so wird die Kombination sein. In anderen Worten, Sie neigen nicht zu kollabieren, die Auswahl der digest in einem schmaleren band.

    Mehr info hier.

    • Eine xor-operation nicht verschwenden bits falls alle input-bits sind unabhängig, aber, wenn es geht-bits, die stark korreliert sind, kann es vergeudet eine Menge. Zum Beispiel, wenn man ein Typ ist ein paar von zahlen im Bereich von 0-65535 und bildet einen hash von xor ' Ing die zahlen zusammen, die oberen 16 bits, die gleich null sind, in der jeder Wert wird mit dem Wert null in die hash-code. Schlimmer ist es, wenn eine unverhältnismäßig große Anzahl von Instanzen (z.B. 10%) müssen beide zahlen übereinstimmen, wird der gleiche Anteil der Instanzen wird null zurückgeben, damit der hash.
    InformationsquelleAutor dogbane
  3. 4

    XOR-operator ist reversibel, d.h. angenommen, ich habe ein bit-string als 0 0 1 und ich XOR mit einem anderen bit-string 1 1 1, die die Ausgabe

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

    Nun kann ich wieder xor der 1. Zeichenfolge mit dem Ergebnis, um die 2. saite. also

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

    So, dass der 2. Zeichenkette mit einem Schlüssel. Dieses Verhalten ist nicht gefunden mit anderen bit-operator

    Sehen Sie sich bitte für mehr Infos --> Warum ist die XOR-Operation verwendet, die auf der Kryptographie?

    • hashCode müssen nicht invertiert werden. //Sorry für mein schlechtes Englisch
    • ja, aber eine Verwendung der XOR in der Kryptographie ist seine Reversibilität der Natur.
    InformationsquelleAutor Bhaskar
  4. 1

    Es ist ein anderer Anwendungsfall: Objekte, die , in denen (einige) Felder verglichen werden müssen, ohne in Bezug auf Ihre Bestellung. Zum Beispiel, wenn Sie wollen, ein paar (a, b) werden immer gleich die paar (b, a).

    XOR hat die Eigenschaft, dass a ^ b = b ^ a, so kann es verwendet werden in hash-Funktion in solchen Fällen.

    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
}

    Verwendung:

            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}
    InformationsquelleAutor Sarge Borsch
Schreibe einen Kommentar