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 toa
.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 index
.
But we are going to use index
to subscript tab
, so it must lie between 0
and tab.length
.
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?
hash
value. The &
does make a difference for negative hash
values.hash
value giving a negative index
value which will lead to an ArrayIndexOutOfBoundsException
.User contributions licensed under CC BY-SA 3.0