RV_ABSOLUTE_VALUE_OF_HASHCODE

· · ─ ·✶· ─ · ·

I had recently written the below code in java to compute the hashcode.

private int hash(String key) { 
    return Math.abs(key.hashCode()) % slots.length; 
}

The idea was to generate the hashcode such that it would always be within 0 and len(slots)-1. Here slots was array so this approach of computing hashcode would allow us to use the hashcode as index to insert some value into the array.

But when findbugs didnt like this and threw an error

High: Bad attempt to compute absolute value of signed 32-bit hashcode in RV_ABSOLUTE_VALUE_OF_HASHCODE

Valid?

Yea. But whats this mean? Findbugs is basically warning us that this approach of computing a hashcode has a problem in a certain edge case scenario.

To understand this better, lets just assume that the size of int is 8 here. What we learn here will apply to 32 bit ints as well.

When key.hashCode() is the most negative value an 8 bit int can hold ie, -128. So now we’re effectively computing 128 % 10 (say length of slots is 10). This gives us back 128. But this cannot be stored in an 8 bit int. So what we actually get back is -128.

This is a valid value for an 8 bit int but its negative and makes no sense as the index for slots.

Ok, how do we fix this?

private int hash(String key) {
    return Math.floorMod(key.hashCode(), slots.length);
}

Math.floorMod() computes the mathematical modulo, rather than Java’s % operator, which computes the remainder.

So -5 % 3 gives us -2. Because java defines a % b = a - (a / b) * b

-5 % 3
= -5 - (-5/3) * 3
= -5 + - (-1) * 3
= -5 + 3
= -2

floorMod() instead uses floor division

-5 = (-2) × 3 + 1

Therefore floorMod(-5, 3) gives back 1.

So floorMod() always gives us back a positive value and within the range of the second parameter.

· · ─ ·✶· ─ · ·