What & Some notations

It allows you to test if an element most likely belongs to a set, or if it absolutely doesn’t.

A Probability method with FP possible, FN never.

Pre-content: True/False Positive/Negative

For a event E, there is a method T try to assert E whether happen or not(T${\oplus}$ or F${\circleddash}$), and we got the final result R(T or F).
The type true or false stand for a state that a result is corresponding the test or not. P/N is meaning the test T's result.

type result
TP Test ${\oplus}$; Result ${\oplus}$
TN Test ${\circleddash}$; Result ${\circleddash}$
FP Test ${\oplus}$; Result ${\circleddash}$
FN Test ${\circleddash}$; Result ${\oplus}$

The worst type is FN because the result just happened as test refer no.

workaround

contents

1. an array arr with structure ${\{0,1\}^n}$, n is the size;
2. hash function ${H(element)}$ to get arr's indices.

workflow

pseudo code:

for i in indices:
if arr[i] == 0:
return false; // element not the part of arr
return true;  //  most likely the part of arr

Pros and Cons

Pros:

1. space efficient;
2. fast;
3. No False Negative

Cons:

1. can't remove element ${\to}$ downgrade by the age;

Distribute(multi-files) the bloom filter files can reduce the effect of cons.1.