overview

Introduction

The Bloom Filter, proposed by Burton Howard Bloom in 1970, is a space-efficient data structure used for testing whether an element is a member of a set. It is composed of a long binary vector and a series of random hash functions. The advantage of the Bloom Filter is that it provides both high space efficiency and fast query time, far exceeding that of general algorithms. However, it suffers from a certain false positive rate and difficulty in removing elements.

The principle behind the Bloom Filter is that when an element is added to the set, it is mapped to K points in a bit array using K hash functions, and these points are set to 1. During retrieval, we simply check if all these points are 1 to determine if the element is likely to be in the set: if any of these points are 0, the element definitely is not in the set; if they are all 1, the element is likely to be in the set. This is the basic idea behind the Bloom Filter.

Reference: https://www.cnblogs.com/z941030/p/9218356.html

Usage

// Initialization
BitMapBloomFilter filter = new BitMapBloomFilter(10);
filter.add("123");
filter.add("abc");
filter.add("ddd");

// Lookup
filter.contains("abc")