Hashing in java hash table

Question

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?

This bit-wise AND will change only negative values of hash to positive values (it clears the sign bit). — Eran
– Eran, Commented Feb 4, 2020 at 7:26

Community · Accepted Answer · 2020-06-20 09:12:55Z

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 a.

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?

Your worked example was for a positive hash value. The & does make a difference for negative hash values.
The point is to avoid a negative hash value giving a negative index value which will lead to an ArrayIndexOutOfBoundsException.

Collectives™ on Stack Overflow

Hashing in java hash table

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related