Я пытаюсь реализовать алгоритм подсчета гиперлога, используя стохастическое усреднение. Для этого мне нужно много независимых универсальных хэш-функций для хэш-элементов в разных субпотоках.Как получить семейство независимых универсальных хеш-функций?
Я обнаружил, что есть только несколько хеш-функций, доступных в hashlib , и, похоже, у меня нет возможности предоставить семя или что-то еще? Я думаю использовать разные соли для разных субпотоков.
Возможно, вам НЕ нужны разные функции хэш-функции. Общим решением этой проблемы является использование только части хэша для вычисления статистики HyperLogLog rho, а другая часть - для выбора подпотока. Если вы используете хорошую хэш-функцию (например, murmur3), она эффективно ведет себя как несколько независимых.
Смотрите раздел «стохастического усреднения» здесь для объяснения этого: https://research.neustar.biz/2012/10/25/sketch-of-the-day-hyperloglog-cornerstone-of-a-big-data-infrastructure/
Однако у Python нет встроенной реализации 'murmur3'; возможно, просто используйте криптографическую хеш-функцию, такую как 'md5', которая даст 128 бит за один раз. –
Хорошая точка, хотя, если вы не ограничены, я бы пошел дальше и потребляю внешнюю реализацию murmur3. В любом случае вам нужно убедиться, что ваша хеш-функция соответствует вашим требованиям скорости (обратите внимание, что криптографические хэш-функции медленны), а также требования к длительности хэш-функции (по крайней мере, 64 бит. 128 - избыток, но у вас нет использовать все биты). – OronNavon
Я не эксперт, но так как там будет столкновения в любом случае вы не можете просто добавить соль пост-хеширование, т.е. к самому хешу? Не уверен, что вы подразумеваете под «независимым», каково фактическое требование/ожидание. – unwind
@unwind Если бы я использовал соль, какие функции библиотеки я должен использовать, потому что я не мог ее найти. –
Извините, рекомендации библиотеки не соответствуют теме переполнения стека. Но в любом случае ... функции хэшлиба [криптографические хэш-функции] (https://en.wikipedia.org/wiki/Cryptographic_hash_function), они _can_ будут использоваться для создания хеш-таблиц и т. Д., Но они относительно медленны. Возможно, вы могли бы сделать что-то с встроенной функцией 'hash()' Python в сочетании с формулой 'h (a, b, x) = (a * x + b)% p% m' из статьи Википедии о [универсальном хэшировании ] (https://en.wikipedia.org/wiki/Universal_hashing#Hashing_integers). –