I've been digging in hash table source code. And found how hashing occurs:
int index = (hash & 0x7FFFFFFF) % tab.length;
I don't understand why bitwise AND used here?
if we turn 0x7FFFFFFF into binary we get = 111 1111 1111 1111 1111 1111 1111 1111
As I know bitwise AND will give 1 if first digit and second = 1
So if we get some object hashcode for example
2314539 turn it into binary and do & operation we actually get the same digit:
2314539 = 10 0011 0101 0001 0010 1011
10 0011 0101 0001 0010 1011 & 11 1111 1111 1111 1111 1111 = 10 0011 0101 0001 0010 1011
10 0011 0101 0001 0010 1011 = 2314539
As you can see this operation doesn't make any changes. So what's a point here?
Let us start with the meaning of remainder (
%) in Java. According to JLS 15.17.3:
The remainder operation for operands that are integers after binary numeric promotion (§5.6.2) produces a result value such that
(a/b)*b+(a%b)is equal to
It follows from this rule that the result of the remainder operation can be negative only if the dividend is negative, and can be positive only if the dividend is positive. Moreover, the magnitude of the result is always less than the magnitude of the divisor.
Suppose that the
index was computed as
index = hash % tab.length. If that were so, a negative value for
hash (the dividend) would result in a negative value for
But we are going to use
index to subscript
tab, so it must lie between
Instead, the actual calculation maps
hash to a non-negative number first by masking out the sign bit. Then it performs the remainder operation.
So what's a point here?
&does make a difference for negative
hashvalue giving a negative
indexvalue which will lead to an
User contributions licensed under CC BY-SA 3.0