Serguey Asael Shinder: Math.abs can return a negative number, and hash bucketing is where it bites
The javadoc for Math.abs(int) is honest about its one surprise. If the argument is not negative, it is returned; if it is negative, its negation is returned. Then: "Note that if the argument is equal to the value of Integer.MIN_VALUE, the most negative representable int value, the result is that same value, which is negative."
The reason is arithmetic, not a bug. As the javadoc for Math.absExact(int) puts it, the range of two's complement integers is asymmetric with one extra negative value, so the mathematical absolute value of Integer.MIN_VALUE does not fit in an int. Negating it wraps around to itself.
The place this matters is a line that appears in a great many codebases:
// pick a shard, partition or bucket for a key
int bucket = Math.abs(key.hashCode()) % buckets;
For almost every key this is fine. For a key whose hash code happens to be Integer.MIN_VALUE, Math.abs returns a negative number, % keeps the sign of the dividend, and the bucket index is negative. With a uniformly distributed hash, that is roughly one key in four billion - rare enough to pass every test and common enough to happen in production eventually, usually as an ArrayIndexOutOfBoundsException far from the code that computed the index. I have not run this here - there is no JDK on the machine I write on - so the behaviour above is taken from the documented contracts rather than from output.
The fix is to stop taking the absolute value at all. Use Math.floorMod(int, int), whose javadoc says the result has the same sign as the divisor or is zero:
// always in 0 .. buckets - 1 for a positive number of buckets
int bucket = Math.floorMod(key.hashCode(), buckets);If you would rather be told when a value cannot be made positive, Math.absExact, available since Java 15, throws ArithmeticException for Integer.MIN_VALUE instead of returning it. The long overloads behave the same way with Long.MIN_VALUE.
A quick search worth doing in any codebase: Math.abs( followed by hashCode() or by anything that feeds a %. Each hit is a one-line change, and each one removes a failure that no test is likely to find.