The shard that can be minus one
A hard Java puzzle in the numeric overflow and precision family. One line below contains a real bug. Try to spot it first, then read why it fails and how to fix it.
Highlighted: line 3. Play this one as a puzzle without the answer.
What is wrong
Math.abs(Integer.MIN_VALUE) is still negative because there is no positive counterpart in two's complement. For the rare key whose hash code is exactly Integer.MIN_VALUE the shard index is negative and the lookup fails. It is rare enough to pass every test and still hit production.
The fix
How to avoid it next time
Use Math.floorMod for bucket indexes. Clearing the sign bit with & 0x7fffffff also works.
Want the background? Read How HashMap works in the Java concepts library.
About numeric overflow and precision
Java integers wrap around silently when they exceed their range, with no exception. int and long arithmetic, integer division and implicit narrowing casts all produce wrong numbers that look plausible.
In code review: Look at the type of every operand, not the type of the variable receiving the result. Multiplication of two ints happens in int even when assigned to a long. Use Math.addExact, long literals and BigDecimal for money.
More puzzles in this family
Frequently asked questions
What is the bug in "The shard that can be minus one"?
Math.abs(Integer.MIN_VALUE) is still negative because there is no positive counterpart in two's complement. For the rare key whose hash code is exactly Integer.MIN_VALUE the shard index is negative and the lookup fails. It is rare enough to pass every test and still hit production. The faulty line is line 3: return Math.abs(key.hashCode()) % shards;
How do I fix it?
Replace it with: return Math.floorMod(key.hashCode(), shards);. Use Math.floorMod for bucket indexes. Clearing the sign bit with & 0x7fffffff also works.
How do I catch numeric overflow and precision in code review?
Look at the type of every operand, not the type of the variable receiving the result. Multiplication of two ints happens in int even when assigned to a long. Use Math.addExact, long literals and BigDecimal for money.
Is there a new puzzle every day?
Yes. The daily Spot the Bug puzzle picks one of these snippets for each UTC day, with the difficulty set by the weekday. Your streak is stored only in your browser.