CODEWITHSUNDEEP
hashhashcodexor
Andrei N
Andrei N

Reputation: 4846

Why are XOR often used in java hashCode() but another bitwise operators are used rarely?

I often see code like

int hashCode(){
  return a^b;
}

Why XOR?

Upvotes: 59

Views: 14985

Answers (4)

Bhaskar
Bhaskar

Reputation: 10681

XOR operator is reversible, i.e. suppose I have a bit string as 0 0 1 and I XOR it with another bit string 1 1 1, the the output is

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

Now I can again xor the 1st string with the result to get the 2nd string. i.e.

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

So, that makes the 2nd string a key. This behavior is not found with other bit operator

Please see this for more info --> Why is XOR used on Cryptography?

Upvotes: 5

Display Name
Display Name

Reputation: 8128

There is another use case: objects in which (some) fields must be compared without regarding their order. For example, if you want a pair (a, b) be always equal to the pair (b, a).
XOR has the property that a ^ b = b ^ a, so it can be used in hash function in such cases.

Examples: (full 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
}

usage:

        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}

Upvotes: 1

dogbane
dogbane

Reputation: 274532

XOR has the following advantages:

  • It does not depend on order of computation i.e. a^b = b^a
  • It does not "waste" bits. If you change even one bit in one of the components, the final value will change.
  • It is quick, a single cycle on even the most primitive computer.
  • It preserves uniform distribution. If the two pieces you combine are uniformly distributed so will the combination be. In other words, it does not tend to collapse the range of the digest into a narrower band.

More info here.

Upvotes: 27

Nils Pipenbrinck
Nils Pipenbrinck

Reputation: 86323

Of all bit-operations XOR has the best bit shuffling properties.

This truth-table explains why:

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

As you can see for AND and OR do a poor job at mixing bits.

OR will on average produce 3/4 one-bits. AND on the other hand will produce on average 3/4 null-bits. Only XOR has an even one-bit vs. null-bit distribution. That makes it so valuable for hash-code generation.

Remember that for a hash-code you want to use as much information of the key as possible and get a good distribution of hash-values. If you use AND or OR you'll get numbers that are biased towards either numbers with lots of zeros or numbers with lots of ones.

Upvotes: 108

Related Questions