Сколько хеш-функций требуется моему цвету-фильтру?

Wikipedia говорит:

Пустой фильтр Bloom - это бит-массив из m бит, все из которых равны 0. Также должны быть определены k различных хеш-функций, каждая из которых отображает или хеширует некоторый элемент набора в одно из положений массива m с равномерным случайным распределение.

Я прочитал статью, но я не понимаю, как определить k. Является ли это функцией размера таблицы?

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

Ответы

Ответ 1

Дано:

  • n: сколько элементов вы ожидаете иметь в своем фильтре (например, 216 553)
  • p: допустимая ложноположительная ставка {0..1} (например, 0.01 → 1%)

мы хотим вычислить:

  • m: количество бит, необходимое в цветном фильтре
  • k: количество хеш-функций, которые мы должны применять

Формулы:

m = -n*ln(p) / (ln(2)^2) количество бит
k = m/n * ln(2) число хеш-функций

В нашем случае:

  • m= -216553*ln(0.01) / (ln(2)^2)= 997263 / 0.48045= 2,075,686 bits (253 kB)
  • k= m/n * ln(2)= 2075686/216553 * 0.693147= 6.46 хэш-функции (7 хэш-функций)

Примечание. Любой код, выпущенный в общественное достояние. Не требуется атрибуция.

Ответ 2

Если вы читаете далее в статью Википедии о фильтрах Bloom, вы найдете раздел "Вероятность ложных срабатываний". В этом разделе объясняется, как количество хеш-функций влияет на вероятности ложных срабатываний и дает формулу для определения k от желаемой ожидаемой проблемы. ложных срабатываний.

Цитата из статьи в Википедии:

Очевидно, вероятность ложной положительность уменьшается как m (число бит в массиве) увеличивается, и увеличивается как n (число вставленных элементов). Для заданных m и n, значение k (число хешей функций), которая минимизирует вероятность

formula