The hashCode()-to-Array-Index Bug Almost Everyone Writes Once

The bug that often trips developers when turning a hash code into an array index looks simple at first: simply applying the modulo operator. However, this innocuous line of code hides two distinct bugs. The fix for one of those bugs, in turn, introduces its own issue. When constructing a HashMap from scratch, the line that maps a key to a bucket index appears straightforward: int bucket = key.hashCode() % capacity; Upon manual tracing of this calculation, a critical error becomes apparent.

The modulo operator (%) returns a signed 32-bit integer result, which can be negative if the dividend is negative. Consider the result of -7 % 16: it is -7, not 9. Feeding this negative index into array[bucket] leads to an ArrayIndexOutOfBoundsException instead of a legitimate but harmless location. The instinct to correct this by wrapping the result in Math.abs() seems promising at first glance.

After all, Math.abs(Integer.MIN_VALUE) returns Integer.MIN_VALUE itself, still negative, which is the intended behavior. However, this approach fails for one specific case: Integer.MIN_VALUE (-2147483648) has no positive counterpart in 32-bit two's complement arithmetic. As a result, Math.abs(Integer.MIN_VALUE) remains negative, thereby failing to guarantee a non-negative result for every possible integer input.

The correct remedy lies in employing Math.floorMod(hash, capacity), a method introduced in Java 8. This function performs a true floored modulo, ensuring non-negative results for positive divisors without any edge cases. Bug two reveals a design choice rather than a flaw in the algorithm itself. Instead of using the modulo operator, java.util.HashMap utilizes the bitwise AND operation (hash & (capacity - 1)).

This bitmask approach only functions correctly when the capacity is a power of two (e.g., 16 - 1 = 15 = 0b01111, a clean sequence of 1-bits). For non-power-of-two capacities, this bitmask operation deviates significantly from true modulo behavior. MyHashMap deviates from this approach by opting for Math.floorMod instead of a bitmask, sacrificing the performance advantage for the flexibility of not enforcing the capacity to be a power of two.

It's essential to be transparent about the chosen method and its underlying rationale, rather than blindly adhering to the JDK's default behavior. Bug three introduces a separate issue that arises even after addressing the previous two bugs. Bitwise operations primarily utilize the lower bits of the hash code. If a class's hashCode() method generates a value with significant variation in its upper bits—a common scenario for certain hash codes such as those derived from floats or sequential object identity—the limited number of buckets may still experience collisions.

This phenomenon occurs despite the hashes being distinct. To mitigate this, java.util.HashMap applies an additional transformation to the hash code by XOR-ing it with shifted bits (h ^ (h << 16)). While this simple operation—consisting of a single shift and one XOR—helps mix the high bits into the lower bits, it's more computationally intensive than the JDK's straightforward approach.

MyHashMap takes this a step further by employing a full FNV-1a hash function over all four bytes of the hashCode, ensuring a more robust mixing of bits. However, this increased complexity comes at the cost of additional computational effort. The decision between these approaches depends on the confidence in the hashCode() distribution of the keys and the frequency of the code path executions.

The JDK's chosen method strikes a balance between simplicity and adequacy for general-purpose use. In conclusion, a seemingly straightforward line of code to map a hash code to an array index can conceal three distinct bugs—each stemming from different aspects of hashing and modulo operations. Understanding these intricacies is crucial for developers to avoid subtle yet pervasive errors in their implementations.