Калькулятор параметров фильтра Блума

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

Как пользоваться

1. Введите ожидаемое количество элементов (n), которые вы планируете вставить в фильтр.
2. Переместите ползунок целевой частоты ложных положительных результатов на требуемую вам точность — более низкие значения означают меньше ложных положительных результатов, но больший битовый массив.
3. Прочитайте размер битового массива (m), количество хеш-функций (k) и требуемую память, а также график, показывающий, как память масштабируется при ужесточении частоты ложных положительных результатов при одном и том же n.

Формулы

• Размер битового массива: m = ceil(-n · ln(p) / (ln 2)²)
• Количество хеш-функций: k = round((m / n) · ln 2), с минимумом 1

Это стандартные формулы оптимальных параметров, используемые всеми основными реализациями фильтра Блума (Guava, BF.RESERVE Redis, pybloom). Поскольку m и k округляются до целых чисел, калькулятор также сообщает фактическую частоту ложных положительных результатов при этих округлённых значениях — используя стандартную оценку (1 - e^(-kn/m))^k — поскольку она редко совпадает с введённым вами целевым значением.

Чтение графика

На графике отображается требуемая память в зависимости от целевой частоты ложных положительных результатов при введённом вами n в логарифмической шкале для частоты ложных положительных результатов. Поскольку m линейно зависит от -ln(p), а ось x имеет шкалу -log₁₀(p), компромисс является прямой линией, а не кривой — ужесточение частоты ложных положительных результатов на порядок величины требует пропорционального и предсказуемого увеличения памяти. Ваше текущее значение отмечено красной точкой.

Ограничения

Это рассчитывает стандартный фильтр Блума (без подсчёта, не масштабируемый) и предполагает идеальное семейство хеш-функций — реальные хеш-функции с коррелированными битами будут немного отличаться от теоретической частоты ложных положительных результатов. Это не учитывает затраты памяти на бит в конкретной реализации языка/библиотеки (некоторые реализации округляют m до степени двойки или кратного размеру машинного слова для более быстрого индексирования), поэтому рассматривайте m/память здесь как теоретический минимум, а не точное выделение, которое сделает ваша библиотека.

Конфиденциальность

Всё работает в вашем браузере — никакие введённые вами данные не отправляются никуда.

Связанные инструменты

Если вам нужен хеш для ключей хранилища фильтра Блума (или что-либо ещё), см. Hash Generator. После того как ваш фильтр будет рассчитан, Cache TTL Calculator поможет вам определить, как долго его записи должны жить, если вы используете его перед кешем.