Всем доброго дня.

Мы запустили новый курс — «Алгоритмы для разработчиков», предназначенных для тех подтянуть знания по разнообразным структурам и алгоритмам обработки данных, решению алгебраических задач и задач динамического программирования для различных языков. Так что сегодня мы делимся небольшой заметкой о работе фильтра Блума в Java.

Введение

В этой статье мы рассмотрим структуру фильтра Блума из библиотеки Guava. Фильтр Юлума — это вероятностная структура данных с эффективным использованием памяти, которую мы можем использовать для ответа на вопрос “Содержится ли данный элемент в множестве?”.

В фильтре Блума не бывает ложноотрицательных, поэтому, если он возвращает false, можно быть уверенным на 100%, что этого элемента в множестве нет.

Однако, фильтр Блума может возвращать ложноположительные, поэтому по возвращении true высока вероятность, что элемент действительно есть в множестве, но вероятность не 100%.

Чтобы узнать подробнее о работе фильтра Блума, ознакомьтесь с этим руководством.



Maven зависимость

Мы будем пользоваться Guava-реализацией фильтра Блума, поэтому добавим Guava-зависимость
Последнюю версию можно найти в Maven Central.

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>22.0</version>
</dependency>

Зачем использовать фильтр Блума?

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

Благодаря своей экономичности, фильтр Блума легко помещается в памяти даже при большом количестве элементов. Некоторые базы данных, включая Cassandra и Oracle, используют этот фильтр для первичной проверки перед обращением к диску или в кэш, например, когда поступает запрос на конкретный ID.

Если фильтр говорит, что ID нет, база данных может перестать обрабатывать запрос и вернуться к клиенту. Иначе, запрос идет на диск и возвращает найденный элемент.

Создание фильтра Блума

Предположим, мы хотим создать фильтр Блума для не более чем 500 целых чисел, и нас утраивает однопроцентная (0.01) вероятность ложноположительных.

Для этого можем воспользоваться классом BloomFilter из библиотеки Guava. Нужно передать количество элементов, сообщаемых фильтру, и желаемую вероятность ложноположительных:

BloomFilter<Integer> filter = BloomFilter.create(
  Funnels.integerFunnel(),
  500,
  0.01);

Теперь добавим некоторые числа в фильтр:

filter.put(1);
filter.put(2);
filter.put(3);

Мы добавили только три элемента и определили максимальное количество вставок — 500, поэтому наш фильтр Блума должен давать довольно точные результаты. Протестируем его с помощью метода mightContain():

assertThat(filter.mightContain(1)).isTrue();
assertThat(filter.mightContain(2)).isTrue();
assertThat(filter.mightContain(3)).isTrue();
 
assertThat(filter.mightContain(100)).isFalse();

Как следует из имени, мы не можем быть на 100% уверены, что данный элемент действительно есть в фильтре, если метод вернул true.

В нашем случае, когда mightContain() возвращает true, 99%, что элемент есть в фильтре, и 1%, что результат ложноположительный. Если фильтр возвращает false, можно быть на 100% уверенным, что элемент отсутствует.

Перенасыщенный фильтр Блума

При проектировании фильтра Блума, важно предоставить достаточно точное значение для ожидаемого количества элементов. Иначе наш фильтр будет возвращать ложноположительные гораздо чаще, чем хотелось бы. Рассмотрим пример.

Предположим, мы создаем фильтр с желаемой вероятностью ложноположительных равной одному проценту и ожидаемым количеством элементов равным пяти, но затем вставляем 100000 элементов:

BloomFilter<Integer> filter = BloomFilter.create(
  Funnels.integerFunnel(),
  5,
  0.01);
 
IntStream.range(0, 100_000).forEach(filter::put);

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

Заметим, что метод mightContatin() возвращает true даже для значения, которое мы ранее не вставляли в фильтр.

Вывод

В этом быстром туториале мы рассмотрели вероятностную природу структуры данных фильтра Блума — с помощью реализации Guava.

Реализацию всех этих примеров и фрагменты кода можно найти в GitHub проекте.

Это Maven-проект, поэтому с импортом и запуском не должно возникнуть сложностей.

THE END

Ждём комментарии и вопросы, которые, как всегда, можно оставить тут, так и зайти на день открытых дверей к преподавателю курса Михаилу Горшкову.