Фильтр Блума в Java с примерами

Опубликовано: 11 Января, 2022

Фильтры Блума предназначены для членства в наборе, которое определяет, присутствует ли элемент в наборе или нет. Фильтр Блума был изобретен Бертоном Х. Блумом в 1970 году в статье под названием « Пространственно-временные компромиссы при хэш-кодировании с допустимыми ошибками» (1970) . Фильтр Блума - это вероятностная структура данных, которая работает с методами хэш-кодирования (аналогично HashTable).

Когда нам понадобится фильтр Блума?
Рассмотрим любую из следующих ситуаций:

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

Можно ли решить эту проблему без помощи Bloom Filter?

Let us try to solve these problem using a HashSet

import java.util.HashSet;
import java.util.Set;
  
public class SetDemo {
    public static void main(String[] args)
    {
        Set<String> blackListedIPs
            = new HashSet<>();
        blackListedIPs.add("192.170.0.1");
        blackListedIPs.add("75.245.10.1");
        blackListedIPs.add("10.125.22.20");
  
        // true
        System.out.println(
            blackListedIPs
                .contains(
                    "75.245.10.1"));
  
        // false
        System.out.println(
            blackListedIPs
                .contains(
                    "101.125.20.22"));
    }
}
Output:

true
false

РЕКОМЕНДУЕМЫЕ СТАТЬИ