XOR hashcode

typical way override hashcode is using bitwise exclusive OR (XOR) :


hashCode(){

return name.hashCode() ^ company.hashCode()

}

 

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.

 

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s