Цель: семейство (далее будет обозначаться как множество всевозможных параметров) быстрых хеш-функций с равномерным распределением. Например, семейство универсальных хеш функций h(k) = ((a*k + b) % p) % m, где a,b - параметры
Проблема: в h(k) (что выше) используется для вычисления 2 взятия по модулю и умножение, что медленно
Нашёл хорошую хорошую хеш функцию CRC-32C: отличное распределение битов +
высокая скорость (3 процессорных цикла (аппаратная....
Сигнатура. Здесь v - входные данные, crc - накопленный циклический код, ну и сам хеш в качестве возвращаемого значения.
unsigned __int64 _mm_crc32_u64 (unsigned __int64 crc, unsigned __int64 v)
Проблема в том, что это единственная хеш функция, не семейство. Можно было бы параметризовать генерирующим полиномом, но тогда не было бы машинной инструкция для crc32 с кастомным полином, что сильно бы её замедлило, а также разные полиномы дают разное распределение хешей (у CRC-32C как уже упоминалось ранее отличное распределение благодраря полиному 0x1EDC6F41), что тоже плохо.
С математической точки зрения можно ли использовать unsigned __int64 crc не как аргумент, а как параметр,
главный вопрос: не может ли это ухудшить относительно равномерное распределение хешей ? И не может ли такого быть, что "похожие" накопленные суммы (параметры хеш функции в данном контексте) дают "похожие" хеши (то есть если будет коллизия с параметром x, то вероятность коллизии с параметром x + 1 такая же как у совершенно случайных параметров x и y) ?
Более формально: Пусть произошла коллизия для v1 != v2: __int64 _mm_crc32_u64(x, v1) = __int64 _mm_crc32_u64(x, v2). Увеличив параметр x на 1, будет ли вероятность коллизии такая же как и у случайных z != y: __int64 _mm_crc32_u64(z, v1) = __int64 _mm_crc32_u64(y, v2) ? То есть вероятности коллизий у __int64 _mm_crc32_u64(z, v1) = __int64 _mm_crc32_u64(y, v2) такие же как и у __int64 _mm_crc32_u64(x + 1, v1) = __int64 _mm_crc32_u64(x + 1, v2), учитывая информацию о коллизии для параметров {x, v1} и {x, v2}
Ну и да, речь идёт о хешировании чисел, не строк или массивов данных, то есть накопленный циклический код (вроде бы) не нужен. Хотя для хешей массивов данных можно использовать этот "параметр" просто в качестве стартового накопленного циклического кода
Простой