Фильтр Блума в Java с примерами
Опубликовано: 11 Января, 2022
Фильтры Блума предназначены для членства в наборе, которое определяет, присутствует ли элемент в наборе или нет. Фильтр Блума был изобретен Бертоном Х. Блумом в 1970 году в статье под названием « Пространственно-временные компромиссы при хэш-кодировании с допустимыми ошибками» (1970) . Фильтр Блума - это вероятностная структура данных, которая работает с методами хэш-кодирования (аналогично HashTable).
Когда нам понадобится фильтр Блума?
Рассмотрим любую из следующих ситуаций:
- Предположим, у нас есть список некоторых элементов, и мы хотим проверить, присутствует ли данный элемент или нет?
- Предположим, вы работаете над почтовой службой и пытаетесь реализовать конечную точку регистрации с функцией, при которой заданное имя пользователя уже присутствует или нет?
- Предположим, вы указали набор 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