Как пользоваться
- В режиме «Размер для заданной доли» введите число элементов и долю ложных срабатываний в процентах (1 — одно ошибочное «да» на сотню проверок отсутствующих элементов).
- Посмотрите число бит, объём памяти в байтах, KiB или MiB и число хеш-функций.
- В режиме «Долю для фильтра» введите n, m в битах и k — получите долю ложных срабатываний и лучшее k для такого размера.
Как это работает
Фильтр Блума — массив из m бит. Каждый элемент выставляет k бит, выбранных k хеш-функциями; проверка смотрит на эти k бит. Формулы:
- m = ⌈−n × ln p ÷ (ln 2)²⌉
- k = round(m ÷ n × ln 2), не меньше 1
- p = (1 − e^(−k × n ÷ m))^k
Так как m округляется вверх, а k — до целого, реальная доля немного отличается от заданной; калькулятор показывает её в строке «Доля при этих m и k».
Пример
Миллион элементов при 1 %:
- m = 1 000 000 × 4,6052 ÷ 0,48045 = 9 585 058,4, вверх — 9 585 059 бит;
- память: 9 585 059 ÷ 8 = 1 198 133 байта, или 1,14 MiB;
- k = 9,585 × 0,6931 = 6,64, округляем до 7 хеш-функций;
- реальная доля при 7 хешах — 1,0039 %, примерно одно ложное срабатывание на 100 проверок.
Советы
- Удвоение размера фильтра не уменьшает долю вдвое, а примерно возводит её в квадрат: 1 % превращается примерно в 0,01 %.
- В коде k хеш-функций можно получить из двух: h1 + i × h2 для i = 0 … k − 1.
- Если элементы нужно удалять, посмотрите на счётные фильтры Блума или фильтры с кукушкиным хешированием.