Я столкнулся с потребностью в k попарно независимых хеш-функциях, каждая из которых принимает в качестве входных данных целое число и выдает хэш-значение в диапазоне от 0 до N. Это нужно для скетча count-min, похожего на фильтр Блума.
Формально мне нужны хэш-функции 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 тоже подойдет или просто алгоритм. Спасибо
