При умножении двух 32-битных целых чисел получается 64-битный результат, но далеко не каждое 64-битное число можно так получить. Эту задачу автор разбирает на примере простой хеш-функции, которая берёт старшие и младшие 16 бит 32-битного числа и перемножает их. Хеш должен давать равномерное распределение, но если провернуть тот же трюк для 64-битных входов (разбить на два 32-битных куска и перемножить), то результат будет покрывать лишь малую долю возможных 64-битных значений.
Ещё Эрдёш доказал: доля 2n-битных чисел, которые являются произведением двух n-битных, стремится к нулю с ростом n. Для небольших n можно посчитать точно. Для 16-битных сомножителей (результат 32 бита) под перемножение попадает примерно одно из пяти чисел – около 20%. Для 32-битных сомножителей (64-битный результат) Уэбстер с коллегами построили математику и опубликовали код. Они выяснили, что существует ровно 3 215 709 724 700 470 902 64-битных беззнаковых целых, которые можно получить как произведение двух 32-битных. Это примерно 17% от всех возможных значений.
Если нужно по произведению восстановить сами сомножители, можно разложить число на простые множители, а затем собрать все возможные делители, меньшие 2³². Алгоритм прост: начинаем с единицы, на каждом простом множителе умножаем текущие кандидаты на все степени этого множителя (не превышая 2³²), потом выбираем максимальный кандидат. Остаток от деления исходного числа на него — второй сомножитель. Если остаток тоже меньше 2³², разложение удалось.
Вывод: если взять случайное 64-битное число, скорее всего его нельзя представить как произведение двух 32-битных. Для хешей это означает, что простая конструкция high * low даёт очень неравномерное распределение, и использовать её не стоит.