Java — каковы варианты для получения k парных независимых хеш-функций, которые быстро

Я столкнулся с необходимостью k попарно независимых хеш-функций, каждая из которых принимает в качестве входных данных целое число и выдает значение хеш-функции в диапазоне 0-N. Нужно это для мини-эскиза, который похож на фильтр Блума.

Формально мне нужны хеш-функции h_1, h_2, …, h_k, попарно независимые.

(h_i (n) mod N) даст значение хеша n в диапазоне 0-N. Хеширование должно быть эффективным по времени, так как я работаю с большим набором данных. В то же время они должны быть как можно более независимыми от пары.

Что я уже пробовал:

1) xxhash: это эффективно, но это нехорошо с точки зрения попарно независимой, что означает, что между хеш-функциями есть хеш-коллизии (то есть h1 (n1) = h1 (n2), тогда некоторые h_k (n1) также = h_k ( n2)) и результат, который я получил, был плохим из-за этого.

2) Аналогично, известный метод целочисленного хеширования ((a * n + b) mod p) mod N также имеет ту же проблему, что и xxhash. Я считаю, что это называется универсальным хешированием

3) Другой, представленный в count-min-sketch, дает довольно хорошие результаты, но занимает слишком много времени для большого ввода.

4) Также попробовал Murmur3, sha1 с аналогичными проблемами при столкновениях.

Любая идея будет принята с благодарностью. C / C ++ предпочтительнее, но Java тоже подойдет, или просто алгоритм.
Спасибо

1

Решение

Я подозреваю, что ваша проблема с методом 2 в том, что вы бросили a_i и b_i, которые были коррелированы.
Работайте в большом поле (где-то около 2 ^ 64) и для начала убедитесь, что все a_i и b_i разные (т.е. вы получаете 2 * k разных чисел). Если они равномерно распределены внутри поля, это также не повредит 🙂

Вы могли столкнуться с той же проблемой в методе 4 с SHA. Большинство криптографических хеш-функций (включая даже сломанные и более старые) намного более чем достаточно для нужд структур данных, будь то независимость по k для любого разумного k или почти для любого другого свойства.
Я бы перепроверил — как ты это использовал?

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]