"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.
Top comments (0)