Выбор минимального размера хэша для заданного допустимого количества коллизий

Question

Я анализирую большое количество данных трассировки сети. Я хочу разделить трассировку на части, хэшировать каждый кусок и сохранять последовательность полученных хэшей, а не исходные фрагменты. Цель моей работы - идентифицировать идентичные порции данных - я хэширую оригинальные порции, чтобы уменьшить размер набора данных для последующего анализа. В моей работе приемлемо, что мы компенсируем вероятность того, что иногда случаются коллизии, чтобы уменьшить размер хеша (например, 40-битный хэш с ошибкой в ​​1% идентичных блоков может превзойти 60-битный хэш с ошибкой в ​​0,001%).

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

Как пример:

1 000 000 фрагментов, подлежащих хэшированию, и мы готовы к ошибочной идентификации в 1% (1% фрагментов хэширования выглядят идентичными, если они не идентичны в исходных данных). Как выбрать хеш с минимальным количеством битов, который удовлетворяет этому?

Я посмотрел материалы, касающиеся Парадокса дня рождения , хотя это касается конкретно вероятности одиночного столкновения. Я также рассмотрел материалы, в которых обсуждается выбор размера на основе приемлемой вероятности одного столкновения, но не смог извлечь из этого правила, как выбрать размер на основе приемлемой вероятности n (или меньше) столкновений.

Answer 1

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

Вопрос в том, что именно вы готовы принять, достаточно ли это, чтобы у вас был ожидаемыйколичество столкновений только на 1% данных?Или вы требуете, чтобы вероятность количества столкновений, проходящих через какую-то границу, была чем-то?Если это первое, то обратная сторона вычисления стиля конверта будет делать:

Ожидаемое количество пар, которые хешируют одно и то же из вашего набора, составляет (1 000 000 C 2) * P (любые два - пара),Предположим, что второе число равно 1 / d, где d - размер хеш-таблицы.(Примечание: ожидания являются линейными, поэтому я пока не слишком обманываю).Теперь вы говорите, что хотите 1% столкновений, то есть всего 10000.Ну, у вас есть (1 000 000 C 2) / d = 10 000, поэтому d = (1 000 000 C 2) / 10 000, что, по данным Google, составляет около 50 000 000.

Итак, вам нужно 50 миллионов возможных значений хеш-функции.Это меньше, чем 2 ^ 26, поэтому вы получите желаемую производительность где-то около 26 бит хеша (в зависимости от качества алгоритма хеширования).Я, наверное, где-то там в 2 раза ошибаюсь, так что вы знаете, это грубо.

Если это автономная задача, вы не можете быть с ограниченным пространством.

Answer 2

Звучит как забавное упражнение!

Кто-то другой мог бы иметь лучший ответ, но я бы пошел по пути грубой силы, при условии, что есть достаточно времени:

Запустите расчет хэширования с использованием добавочного размера хеша и запишите процент коллизий для каждого размера хеша.

Возможно, вы захотите использовать бинарный поиск, чтобы уменьшить пространство поиска.