Реализация фильтра Блума с использованием Java
Реализация фильтра Блума с использованием Java

Реализация фильтра Блума с использованием Java

Предисловие

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

Введение в фильтры Блума

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

Принцип действия фильтра Блума

  1. Фильтр Блума состоит из битового массива (массива, содержащего множество битов) и нескольких хеш-функций.
  2. Сначала инициализируйте битовый массив и установите все биты в 0.
  3. Когда элемент необходимо добавить в набор, для хеширования элемента и получения нескольких хеш-значений используются несколько хеш-функций.
  4. Установите позиции битового массива, соответствующие этим значениям хеш-функции, равными 1.
  5. Когда вам нужно запросить, находится ли элемент в наборе, вы также используете ту же хеш-функцию для вычисления хеш-значения и определения значения соответствующей позиции битового массива. Если значение любой из позиций равно 0, это означает, что значение любой из позиций равно 0. что элемент не должен быть в наборе. Если значение во всех позициях равно 1, элемент, вероятно, находится в наборе.

Возможности фильтра Блума

  • Фильтры Блума очень хорошо справляются с крупномасштабными сборами данных, а скорость запросов очень высокая, а временная сложность составляет O(1).
  • Фильтр Блума будет иметь определенную частоту ошибочных оценок, то есть существует определенная вероятность «неправильной оценки и пропущенного определения», поскольку значения хеш-функции, соответствующие нескольким различным элементам, могут попасть в одну и ту же битовую позицию, что приведет к неправильной оценке.
  • Фильтры Блума подходят для сценариев обработки, в которых допустим определенный уровень ложных срабатываний, например дедупликация. URL-адресов при веб-сканирование, решение проблемы проникновения кэша и т.д.

Сценарии применения фильтра Блума

  1. Дедупликация URL-адресов при веб-сканировании：В гусеничной системе,Фильтры Блума могут помочь быстро определить, был ли просканирован URL-адрес.,Избегайте повторного сканирования.
  2. Проблема с проникновением в кэш решена：в системе кэширования,Фильтр Блума может быстро определить, существует ли запрошенный ключ.,тем самым сокращая количество запросов к внутреннему хранилищу.,Избегайте проблем с проникновением в кэш.
  3. Блокировать вредоносные запросы：в приложениях сетевой безопасности,Фильтры Блума можно использовать для быстрой фильтрации некоторых известных вредоносных запросов.,Уменьшите нагрузку на сервер.
  4. Дедупликация данных：Операции дедупликации больших объемов данных,Фильтры Блума могут снизить затраты на определение фактического веса.,Повышение эффективности обработки данных.

Реализация фильтра Блума с использованием Java

Вот пример простой реализации фильтра Блума в Java-коде:

Язык кода:javascript
копировать
import java.util.BitSet;
public class SimpleBloomFilter {
    private BitSet bitSet;
    private int size;
    private int hashFuncs;
    public SimpleBloomFilter(int size, int hashFuncs) {
        this.size = size;
        this.hashFuncs = hashFuncs;
        bitSet = new BitSet(size);
    }
    public void add(String element) {
        for (int i = 0; i < hashFuncs; i++) {
            int hash = (element + i).hashCode() % size;
            bitSet.set(hash, true);
        }
    }
    public boolean contains(String element) {
        for (int i = 0; i < hashFuncs; i++) {
            int hash = (element + i).hashCode() % size;
            if (!bitSet.get(hash)) {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        SimpleBloomFilter bloomFilter = new SimpleBloomFilter(100, 3);
        bloomFilter.add("apple");
        bloomFilter.add("banana");
        
        System.out.println(bloomFilter.contains("apple"));  // выход true
        System.out.println(bloomFilter.contains("orange")); // выход false
    }
}

В приведенном выше коде,Мы реализовали простой фильтр БлумаSimpleBloomFilter。Определяем битовый массивbitSet、размер фильтраsizeи количество хэш-функцийhashFuncs,И реализует функции добавления элементов и проверки существования элементов.

Примеры сценариев применения

Введение в сценарии применения

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

действительный Примеры сценариев применения：URLУдалить дубликаты

В системах сканирования один и тот же URL-адрес часто сканируется повторно. Чтобы повысить эффективность и сэкономить ресурсы, фильтры Блума можно использовать для реализации дедупликации URL-адресов и уменьшения количества повторных обходов.

Язык кода:javascript
копировать
import java.util.BitSet;
import java.util.HashSet;
public class UrlDuplicateChecker {
    private BitSet bitSet;
    private int size;
    private int hashFuncs;
    
    public UrlDuplicateChecker(int size, int hashFuncs) {
        this.size = size;
        this.hashFuncs = hashFuncs;
        bitSet = new BitSet(size);
    }
    
    public void addUrl(String url) {
        for (int i = 0; i < hashFuncs; i++) {
            int hash = (url + i).hashCode() % size;
            bitSet.set(hash, true);
        }
    }
    
    public boolean isUrlDuplicate(String url) {
        for (int i = 0; i < hashFuncs; i++) {
            int hash = (url + i).hashCode() % size;
            if (!bitSet.get(hash)) {
                return false;
            }
        }
        return true;
    }
    
    public static void main(String[] args) {
        UrlDuplicateChecker urlChecker = new UrlDuplicateChecker(1000, 3);
        
        // Имитировать добавление повторяющихся URL-адресов
        urlChecker.addUrl("https://www.example.com/page1");
        urlChecker.addUrl("https://www.example.com/page2");
        urlChecker.addUrl("https://www.example.com/page1");
        
        // Проверьте, не дублируется ли URL-адрес
        System.out.println("Is https://www.example.com/page1 duplicate: " + urlChecker.isUrlDuplicate("https://www.example.com/page1"));
        System.out.println("Is https://www.example.com/page3 duplicate: " + urlChecker.isUrlDuplicate("https://www.example.com/page3"));
    }
}

В приведенном выше примере,Мы создалиUrlDuplicateCheckerдобрый,Имитирует сценарий дедупликации URL. Мы используем фильтр Блума для выявления повторяющихся URL-адресов.,Уменьшите количество сканирования повторяющихся URL-адресов.,Повысьте эффективность гусеничной системы.

действительный Примеры сценариев применения：Дедупликация данных

Язык кода:javascript
копировать
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.nio.charset.Charset;
public class BloomFilterDemo {
    public static void main(String[] args) {
        // Инициализируйте фильтр Блума, установите количество элементов, которые, как ожидается, будут обработаны, равным 10 000, а ожидаемый уровень ложных срабатываний равен 0,01.
        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), 10000, 0.01);
        // Моделирование Дедупликация сцена данных, добавьте несколько элементов
        bloomFilter.put("apple");
        bloomFilter.put("banana");
        bloomFilter.put("orange");
        // Определить, находится ли элемент в фильтре Блума
        System.out.println("Is 'apple' in filter: " + bloomFilter.mightContain("apple"));
        System.out.println("Is 'grape' in filter: " + bloomFilter.mightContain("grape"));
        System.out.println("Is 'banana' in filter: " + bloomFilter.mightContain("banana"));
    }
}

BloomFilter, предоставленный библиотекой Google Guava для реализации фильтра Блума. первый,Инициализируем фильтр Блума,Устанавливает количество элементов, которые, как ожидается, будут обработаны, равным 10000.,Ожидаемый уровень ложных срабатываний составляет 0,01. Затем,Мы добавили несколько элементов в фильтр Блума,и проверил, находятся ли некоторые элементы в фильтре Блума. По характеристикам фильтра Блума,Для добавленных элементов,mightContainМетод вернетtrue；Для элементов, которые не добавляются,Хотя существует определенная доля ошибочных суждений,Но в этом случае шансы невелики. так,Мы можем использовать фильтры Блума для быстрой дедупликации данных.

действительный Примеры сценариев применения：Блокировать вредоносные

Язык кода:javascript
копировать
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.nio.charset.Charset;
public class MaliciousRequestFilter {
    private static final int EXPECTED_INSERTIONS = 1000;
    private static final double FALSE_POSITIVE_PROBABILITY = 0.01;
    private BloomFilter<String> bloomFilter;
    public MaliciousRequestFilter() {
        bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), EXPECTED_INSERTIONS, FALSE_POSITIVE_PROBABILITY);
    }
    public void addMaliciousRequest(String requestId) {
        bloomFilter.put(requestId);
    }
    public boolean isMaliciousRequest(String requestId) {
        return bloomFilter.mightContain(requestId);
    }
    public static void main(String[] args) {
        MaliciousRequestFilter filter = new MaliciousRequestFilter();
        // Имитировать добавление вредоносных запросов в фильтр Блума
        filter.addMaliciousRequest("malicious_request_1");
        filter.addMaliciousRequest("malicious_request_2");
        // Имитация, чтобы определить, является ли запрос вредоносным
        System.out.println("Is 'normal_request' malicious: " + filter.isMaliciousRequest("normal_request")); // должно вернуть ложь
        System.out.println("Is 'malicious_request_1' malicious: " + filter.isMaliciousRequest("malicious_request_1")); // должно вернуть истину
    }
}

В приведенном выше коде,Мы создалиназванныйMaliciousRequestFilterиздобрый,Он содержит инициализацию графина Блума.、Добавьте вредоносные запросы и методы, чтобы определить, является ли запрос вредоносным.。существоватьmainв методе,Мы создаем экземплярMaliciousRequestFilterдобрый,И добавил выявление двух вредоносных запросов. впоследствии,Мы делаем это, вызываяisMaliciousRequestМетод определения того, является ли запрос вредоносным。Если фильтр Блума считает, что запрос может быть вредоносным,ТакisMaliciousRequestМетод вернетtrue,В противном случае вернитеfalse。так,Мы можем использовать фильтр Блума, чтобы быстро блокировать конкурентные запросы.,Уменьшите нагрузку на сервер.

Фактические примеры применения: проблема с проникновением в кэш.

Язык кода:javascript
копировать
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.nio.charset.Charset;
import java.util.HashMap;
import java.util.Map;
public class CacheWithBloomFilter {
    private Map<String, String> cache = new HashMap<>();
    private BloomFilter<String> bloomFilter;
    public CacheWithBloomFilter() {
        bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), 1000, 0.01);
    }
    public String getDataFromCache(String key) {
        if (bloomFilter.mightContain(key)) {
            return cache.get(key);
        } else {
            // Simulate fetching data from database or external service
            String data = fetchDataFromDatabase(key);
            if (data != null) {
                cache.put(key, data);
                bloomFilter.put(key);
            }
            return data;
        }
    }
    private String fetchDataFromDatabase(String key) {
        // Simulating fetching data from database
        if (key.equals("key1")) {
            return "Data for key1";
        }
        return null;
    }
    public static void main(String[] args) {
        CacheWithBloomFilter cacheWithBloomFilter = new CacheWithBloomFilter();
        
        // Fetch data for key1 - cache miss, fetch data from database
        System.out.println(cacheWithBloomFilter.getDataFromCache("key1"));
        
        // Fetch data for key1 again - cache hit
        System.out.println(cacheWithBloomFilter.getDataFromCache("key1"));
        
        // Fetch data for key2 - cache miss, data not available in database
        System.out.println(cacheWithBloomFilter.getDataFromCache("key2"));
    }
}

Подвести итог

Фильтр Блума — очень практичная структура данных.,Это может повысить эффективность запросов и снизить нагрузку на систему во многих сценариях. Через введение и пример кода в этой статье,Надеюсь, читатели имеют предварительное представление о принципе действия фильтра Блума и его реализации.,И может гибко применяться в реальных проектах. Если вам нужна более сложная и эффективная реализация фильтра Блума,Можно добиться дальнейшего углубленного изучения и оптимизации.

boy illustration
Неразрушающее увеличение изображений одним щелчком мыши, чтобы сделать их более четкими артефактами искусственного интеллекта, включая руководства по установке и использованию.
boy illustration
Копикодер: этот инструмент отлично работает с Cursor, Bolt и V0! Предоставьте более качественные подсказки для разработки интерфейса (создание навигационного веб-сайта с использованием искусственного интеллекта).
boy illustration
Новый бесплатный RooCline превосходит Cline v3.1? ! Быстрее, умнее и лучше вилка Cline! (Независимое программирование AI, порог 0)
boy illustration
Разработав более 10 проектов с помощью Cursor, я собрал 10 примеров и 60 подсказок.
boy illustration
Я потратил 72 часа на изучение курсорных агентов, и вот неоспоримые факты, которыми я должен поделиться!
boy illustration
Идеальная интеграция Cursor и DeepSeek API
boy illustration
DeepSeek V3 снижает затраты на обучение больших моделей
boy illustration
Артефакт, увеличивающий количество очков: на основе улучшения характеристик препятствия малым целям Yolov8 (SEAM, MultiSEAM).
boy illustration
DeepSeek V3 раскручивался уже три дня. Сегодня я попробовал самопровозглашенную модель «ChatGPT».
boy illustration
Open Devin — инженер-программист искусственного интеллекта с открытым исходным кодом, который меньше программирует и больше создает.
boy illustration
Эксклюзивное оригинальное улучшение YOLOv8: собственная разработка SPPF | SPPF сочетается с воспринимаемой большой сверткой ядра UniRepLK, а свертка с большим ядром + без расширения улучшает восприимчивое поле
boy illustration
Популярное и подробное объяснение DeepSeek-V3: от его появления до преимуществ и сравнения с GPT-4o.
boy illustration
9 основных словесных инструкций по доработке академических работ с помощью ChatGPT, эффективных и практичных, которые стоит собрать
boy illustration
Вызовите deepseek в vscode для реализации программирования с помощью искусственного интеллекта.
boy illustration
Познакомьтесь с принципами сверточных нейронных сетей (CNN) в одной статье (суперподробно)
boy illustration
50,3 тыс. звезд! Immich: автономное решение для резервного копирования фотографий и видео, которое экономит деньги и избавляет от беспокойства.
boy illustration
Cloud Native｜Практика: установка Dashbaord для K8s, графика неплохая
boy illustration
Краткий обзор статьи — использование синтетических данных при обучении больших моделей и оптимизации производительности
boy illustration
MiniPerplx: новая поисковая система искусственного интеллекта с открытым исходным кодом, спонсируемая xAI и Vercel.
boy illustration
Конструкция сервиса Synology Drive сочетает проникновение в интрасеть и синхронизацию папок заметок Obsidian в облаке.
boy illustration
Центр конфигурации————Накос
boy illustration
Начинаем с нуля при разработке в облаке Copilot: начать разработку с минимальным использованием кода стало проще
boy illustration
[Серия Docker] Docker создает мультиплатформенные образы: практика архитектуры Arm64
boy illustration
Обновление новых возможностей coze | Я использовал coze для создания апплета помощника по исправлению домашних заданий по математике
boy illustration
Советы по развертыванию Nginx: практическое создание статических веб-сайтов на облачных серверах
boy illustration
Feiniu fnos использует Docker для развертывания личного блокнота Notepad
boy illustration
Сверточная нейронная сеть VGG реализует классификацию изображений Cifar10 — практический опыт Pytorch
boy illustration
Начало работы с EdgeonePages — новым недорогим решением для хостинга веб-сайтов
boy illustration
[Зона легкого облачного игрового сервера] Управление игровыми архивами
boy illustration
Развертывание SpringCloud-проекта на базе Docker и Docker-Compose
©