# Hashing in java hash table

3

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?

java
hash
hashtable

3

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?

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

User contributions licensed under CC BY-SA 3.0