Hashtable hashing avoid negative hashcode

Question

I am wondering why does Hashtable avoid using negative hashcode ?

int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

Where (hash & 0x7FFFFFFF) makes the signed bit to be 0 to positive, but why couldn't we treat the signed 32 bit integer as unsigned ? or even use the modular tricks to make it become positive. For example,

public static long int_mod(int hashcode, int tab_length){
     return (hashcode % tab_length + tab_length) % tab_length;  
} 

Answer 1

The value has to be between 0 and tab.length - 1 because it is used as an index into an internal array (tab in this case) storing the values (and overflow elements). Therefore, it cannot be negative.

I assume (hash & 0x7FFFFFFF) % tab.length is used in preference of (hashcode % tab.length + tab.length) % tab.length because it is faster without unduly increasing the chance of collisions, but you would have to find a design document or talk to the original developers to know for sure.

Answer 2

... but why couldn't we ...

You're asking why a particular implementation was chosen. Nobody can tell you that, except maybe the original author of the code, if he or she remembers.

There are always multiple ways to implement an idea in code. The person that's writing the code has to choose one of them. It doesn't make a lot of sense to ask, after the fact, why another particular implementation wasn't chosen.

Answer 3

If you keep your capacity a power of 2,

private static final int CAPACITY = 64;
private static final int HASH_MASK = CAPACITY - 1;

final int index = obj.hashCode() & HASH_MASK;

Basically, mask out all but the lower bits in which you are interested. Assuming the lower N bits has as even of a distribution as the entire hash code.