A probabilistic data structure that tests whether an element is a member of a set. Never has false negatives, but can have rare false positives. Uses a tiny bit array.
time:O(k) — k hash functions
space:O(m) — m bits
⚡ +400_XP
step[1/10]
> Init
0
0
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
0
9
0
10
0
11
0
12
0
13
0
14
0
15
0
▸A Bloom Filter is a bit array of 16 bits, all starting at 0. It uses 3 hash functions to check set membership with zero false negatives.
// tap NEXT STEP to walk through one step at a time