Как равномерно распределить целые числа по 16 бакетам

Что проверяют

Видите ли вы, что «просто взять остаток» ломается на отрицательных числах и на входе с закономерностью. Следом обычно спрашивают, что делает HashMap со слабыми хэшами и что будет, если число бакетов изменится.

Как отвечать

Сначала уточните условие: числа произвольные или известны заранее, есть ли отрицательные, должно ли распределение быть детерминированным. От этого зависит решение.

• остаток: n % 16 в Java для отрицательного n даёт отрицательный результат, -3 % 16 равно -3, то есть индекс за пределами массива. Правильно Math.floorMod(n, 16);
• маска: раз 16 это степень двойки, n & 15 даёт индекс от 0 до 15 для любого int, включая отрицательные, и обходится дешевле деления;
• перемешивание битов: и остаток, и маска берут только младшие 4 бита. Если все числа кратны 16 (шаг идентификаторов, выровненные адреса), они лягут в один бакет. Поэтому биты сначала перемешивают: HashMap делает h ^ (h >>> 16), а надёжнее мультипликативное хэширование (n * 0x9E3779B9) >>> 28, которое берёт старшие 4 бита произведения, зависящие от всех битов числа;
• равное количество: если нужны бакеты строго одинакового размера и данные известны заранее, это уже не хэширование. Отсортируйте и разрежьте на 16 частей по квантилям или раскладывайте по позиции i % 16.

Проверить равномерность просто: прогнать миллион значений, посчитать заполнение каждого бакета и сравнить с ожидаемым, для строгости критерием хи-квадрат.

Если число бакетов будет меняться, скажите про консистентное хэширование: при переходе с 16 на 17 обычный остаток переселит почти все ключи, а консистентная схема только примерно семнадцатую часть.

Где спотыкаются

Пишут number % 16 и не думают про минус. На первом отрицательном числе получают ArrayIndexOutOfBoundsException.

Чинят через Math.abs(n) % size. Для Integer.MIN_VALUE модуль остаётся отрицательным, и при числе бакетов, не равном степени двойки, индекс снова уходит в минус.

Считают, что остаток сам по себе даёт равномерность. Он равномерен только для равномерного входа, а на реальных данных с шагом или выравниванием распределение перекашивается, и часть бакетов переполняется.