Hash hash tables eliminate negative hash

Question

I am wondering why hashtable avoid using negative hash code?

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

Where (hash & 0x7FFFFFFF) makes the bit-bit at 0 positive, but why can't we treat the signed 32-bit integer as unsigned? or even use modular tricks to make it 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 must be between 0 and tab.length - 1 , because it is used as an index in the internal array ( tab in this case), storing the values ​​(and overflow elements). Therefore, it cannot be negative.

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

Answer 2

... but why can't we ...

You ask why a particular implementation was chosen. No one can tell you this, except perhaps the original author of the code, if he or she remembers.

There are always several ways to implement an idea in code. The person who writes the code must choose one of them. It makes no sense to ask after why another particular implementation has not been selected.

Answer 3

If you keep your power at 2,

 private static final int CAPACITY = 64; private static final int HASH_MASK = CAPACITY - 1; final int index = obj.hashCode() & HASH_MASK; 

Basically mask everything except the low-order bits you are interested in. Assuming that the lower N bits have as distribution throughout the hash code.

Answer 4

Java does not have its own unsigned type. If hashCode has negative values, we will have to use such masking tricks, everywhere we use hashCode as an index in an array.

Answer 5

There is supposedly a great reason why we cannot consider a signed int as unsigned: the original Java developers thought unsigned support was an unnecessary complication, since unsigned arithmetic could be confused . Since then, this has not been a problem for Java.

As verdesmerald mentioned , since there is no clear record of why (hash & 0x7FFFFFFF) % tab.length was chosen because of your smart modding, although we can find justifications for the solution, in the end we can only reflect on why this was done.

One endpoint of semantics, which is probably not so important: it is not so much that the Hashtable does not use negative hash codes, because the hash codes are “translated” into non-negative form for the index.

Answer 6

No one can tell you why the original author chose this implementation, except for himself (and, possibly, his colleagues). It doesn't make any difference because it works great.

That your proposed implementation: probably it doesn’t do what you think should do. You should update what the% operator in java really does: For example, here . Add integer overflow to the mix, and the proposed expression may lead to negative values ​​...