Сколько хеш-функций нужно моему фильтру Блума?

Question

Википедия говорит:

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

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

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

Answer 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 бит (253 кБ)
• k = m/n * ln(2) = 2075686/216553 * 0.693147 = 6.46 хеш-функции (7 хеш-функций)

Примечание : любой код, опубликованный в открытом доступе. Указание авторства не требуется.

Answer 2

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

---

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

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

Answer 3

И выложить его в аккуратный столик:

http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html

Answer 4

Отличный онлайн-калькулятор Bloomfilter .

Этот интерактивный калькулятор фильтра Блума позволяет вам оценить и выяснить коэффициенты для ваших нужд фильтра Блума. Он также показывает вам графики, чтобы увидеть результаты визуально и предоставляет все формулы Например, расчеты для 216 553 n предметов с вероятностью p 0,01:

n = ceil(m / (-k / log(1 - exp(log(p) / k))))
p = pow(1 - exp(-k / (m / n)), k)
m = ceil((n * log(p)) / log(1 / pow(2, log(2))));
k = round((m / n) * log(2));

Answer 5

Учитывая количество битов на ключ, которые вы хотите «инвестировать», наилучшим k будет:

max(1, round(bitsPerKey * log(2)))

Где max - старшее из двух, round округляет до ближайшего целого числа, log - натуральный логарифм (основание e).