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

"hash % capacity" looks trivial until you trace it by hand. Two separate bugs hide in that one line — and the fix for one of them has its own hole. Building a HashMap from scratch, the "turn a key into a bucket index" line looks like it should be the easy part: int bucket = key.hashCode() % capacity; I traced this by hand before writing a single line of MyHashMap, and it broke immediately — for a reason that has nothing to do with hashing. Bug one: % isn't modulo hashCode() returns a signed 32-bit int — anything from Integer.MIN_VALUE to Integer.MAX_VALUE, including negative numbers. Trace -7 % 16 in Java by hand before reading the next sentence. Java's % is a remainder operator, not mathematical modulo — the result takes the sign of the dividend, not the divisor. -7 % 16 is -7, not 9. Feed that straight into array[bucket] and you get an ArrayIndexOutOfBoundsException, not a wrong-but-harmless bucket. The naive fix has its own hole First instinct: wrap it in Math.abs(). int bucket = Math.abs(key.hashCode() % capacity); // looks fixed. isn't, always. This works for almost every input — and then silently breaks on exactly one value. Integer.MIN_VALUE (-2147483648) has no positive counterpart in 32-bit two's complement — the range is -2147483648 to 2147483647, one more negative number than positive. Math.abs(Integer.MIN_VALUE) returns Integer.MIN_VALUE itself, still negative. It's documented behavior, not a JVM bug — and it means Math.abs() doesn't actually guarantee a non-negative result for every int, which defeats the entire point of reaching for it here. The actual fix Math.floorMod(hash, capacity), added in Java 8, does true floored modulo — always non-negative for a positive divisor, no edge case: private int getBucket(K key, int length) { int hashCode = key.hashCode(); int hash = fnvHash(hashCode); int bucket = Math.floorMod(hash, length); return bucket; } Bug two (a design choice, really): bitmask vs. modulo java.util.HashMap doesn't use modulo at all — it uses hash & (capacity - 1), a bitmask. That only works correctly when capacity is a power of two: 16 - 1 = 15 = 0b01111, a clean run of 1-bits that extracts exactly the low 4 bits regardless of the input's sign. Try it with a non-power-of-two capacity and the mask stops behaving like a clean modulo at all. In exchange for that constraint, bitmask AND is measurably faster than a division-based modulo — division/remainder is one of the more expensive basic ALU operations, and benchmarks commonly show bitmask coming out several times faster at scale. MyHashMap deliberately went the other way: Math.floorMod instead of a bitmask, trading that speedup for not forcing capacity to always be a power of two. Worth being honest about which one you're picking and why, rather than defaulting to whichever the JDK does without registering there's a choice at all. Bug three: fixing the sign doesn't fix distribution Even with a correct, always-non-negative index, there's a separate problem hiding underneath. Bitmask (and, to a lesser extent, modulo) only meaningfully uses the low bits of the hash. If a class's hashCode() implementation happens to vary mostly in its high bits — this is common, not hypothetical (float-derived hashes and sequential object-identity hashes are classic examples) — a small table can collide those distinct hashCodes into the same few buckets, even though the hashCodes themselves are all different. This is why java.util.HashMap doesn't use a key's raw hashCode() — it runs it through h ^ (h >>> 16) first: shift the top 16 bits down, XOR them into the bottom 16. Cheap — one shift, one XOR — and it's enough to fold high-bit entropy into the bits that actually get used for indexing. MyHashMap goes further: a full FNV-1a mix over all four bytes of the hashCode, not just a single XOR-fold: private static int fnvHash(int hashCode) { int hash = STARTING_SEED; // 0x811C9DC5, the FNV offset basis for (int shift = 24; shift >= 0; shift -= 8) { byte b = (byte) ((hashCode >> shift) & 0xFF); hash ^= (b & 0xFF); hash *= 0x01000193; // FNV prime, 32-bit } return hash; } This is a genuine cost/benefit tradeoff, not a strict improvement: four iterations of shift/XOR/multiply per hash call is meaningfully more work than the JDK's single shift-and-XOR. Whether that's worth it depends on how confident you are in your keys' hashCode() distribution and how hot the code path is — the JDK's choice is "cheapest fix that's good enough for general-purpose use," not "best possible mixing." Takeaway One line, three separate bugs, none of them about hashing itself: sign handling (and a naive fix for it that has its own edge case), a speed/flexibility tradeoff in how you reduce to a valid range, and a distribution problem that survives fixing the first two. Trace -7 % 16 by hand before you trust any "obviously correct" indexing line again. Further reading Full Source Code Gist Modulo of Negative Numbers — Torsten Curdt Best Way to Fix Java's Modulus with Negative Numbers — javathinking.com The Power of the "Power of Two" — Medium Algorithms, 4th ed. — Hash Tables (Sedgewick & Wayne)