Small Implementation: Bucket Index

Bucket index from hash code and table length: typically (hash & 0x7fffffff) % capacity or bit masking with power of two.

$$i=(h\mathbin{\&}\mathtt{0x7fffffff})\bmod m$$

Where used

Modulo or bit masking to the capacity is the core of every hash container. Errors here (negative hash, incorrect capacity) are typical implementation bugs.

Depth

A bucket index must lie for every possible hash value in the range from zero to capacity minus one. In Java, Math.floorMod(hash, capacity) is a direct formulation of this invariant. A simple absolute value calculation is problematic with Integer.MIN_VALUE, because its positive counterpart cannot be represented in the int range.

The capacity must be positive. In cases where capacities are powers of two, some implementations use bit masks but often mix high and low hash bits beforehand. Without this mixing, regular bit patterns could overload the lower positions excessively.

Difficulty levels

1. Determine indices for positive and negative hash values.
2. Explain the special case of the smallest int value.
3. Compare modulo mapping and bit masking under appropriate conditions.

Pitfalls

Math.abs(hash) % capacity is not safe for all int values. Likewise, a capacity of zero does not lead to a meaningful bucket but to an arithmetic error.