Как получить в семье независимую универсальную хеш-функцию?

Question

Я пытаюсь реализовать алгоритм подсчета гиперлоглогов с использованием стохастического усреднения. Для этого мне нужно много независимых универсальных хеш-функций для хеширования элементов в разных подпотоках.

Я обнаружил, что в hashlib доступно всего несколько хеш-функций, и, похоже, у меня нет возможности предоставить начальное число или что-то еще? Я думаю использовать разные соли для разных подпотоков.

Answer 1

Возможно, вам не нужны разные хеш-функции. Распространенным решением этой проблемы является использование только части хэша для вычисления статистики HyperLogLog rho, а другой части - для выбора подпотока. Если вы используете хорошую хеш-функцию (например, murmur3), она фактически ведет себя как несколько независимых.

См. Раздел "Стохастическое усреднение" здесь для объяснения этого: https://research.neustar.biz/2012/10/25/sketch-of-the-day-hyperloglog-cornerstone-of-a-big-data-infrastructure/