53

のようなコードをよく見かけます。

int hashCode(){
  return a^b;
}

XOR を使用する理由

4

4 に答える 4

100

すべてのビット操作の中で、XOR は最高のビット シャッフル プロパティを備えています。

この真理値表はその理由を説明しています:

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

ご覧のとおり、AND と OR はビットの混合がうまくいきません。

OR は、平均して 3/4 の 1 ビットを生成します。一方、AND は平均 3/4 ヌル ビットを生成します。XOR のみが偶数 1 ビット対ヌル ビット分布を持ちます。そのため、ハッシュコード生成にとって非常に価値があります。

ハッシュコードの場合、できるだけ多くのキーの情報を使用し、ハッシュ値の適切な分散を取得する必要があることに注意してください。AND または OR を使用すると、多数のゼロを含む数値または多数の 1 を含む数値に偏った数値が得られます。

于 2010-02-25T13:27:15.467 に答える
23

XOR には次の利点があります。

  • 計算の順序に依存しません。つまり、a^b = b^a
  • ビットを「浪費」しません。コンポーネントの 1 つでも 1 ビットでも変更すると、最終的な値が変更されます。
  • 最も原始的なコンピューターでも 1 サイクルで済みます。
  • 一様分布を維持します。組み合わせた 2 つのピースが均一に分布している場合、組み合わせは均一になります。つまり、ダイジェストの範囲を狭帯域に崩す傾向がありません。

詳細はこちら。

于 2010-02-25T13:32:36.297 に答える
5

XOR 演算子は可逆です。つまり、ビット文字列が0 0 1あり、それを別のビット文字列と XOR すると1 1 1、出力は次のようになります。

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

これで、最初の文字列と結果を xor して、2 番目の文字列を取得できます。すなわち

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

つまり、2 番目の文字列がキーになります。この動作は他のビット演算子では見られません

詳細については、こちらを参照してください -->暗号化で XOR が使用されるのはなぜですか?

于 2010-02-25T13:32:13.743 に答える
1

別の使用例があります: (一部の) フィールドを順序に関係なく比較する必要があるオブジェクト。たとえば、ペア(a, b)を常にペアにしたい場合(b, a)。
XOR はa ^ b=という性質を持っているb ^ aので、そのような場合にハッシュ関数で使用できます。

例: (完全なコードはこちら)

意味：

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
}

利用方法：

        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}
于 2014-03-23T13:25:59.190 に答える