HashingHashing

Bloom Filter

A bit array plus k hash functions that answers "possibly in the set" or "definitely not" in O(k) with a tiny memory footprint and no false negatives.

Learn Bloom Filter →
0
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
16
0
17
0
18
0
19
0
20
0
21
0
22
0
23
0
24
0
25
0
26
0
27
0
28
0
29
0
30
0
31
1/40An empty filter: 32 bits, all zero, and no keys stored anywhere. A Bloom filter never keeps the keys themselves — it keeps only the marks that 3 hash functions leave, which is why it costs a few bits per key instead of a few bytes.
Bit position just hashed toBit is 1Probed bit was 1 (consistent with present)Probed bit was 0 (proves absence)Bit is still 0
PseudocodeLearn Bloom Filter →
1insert(key):                                  # m = 32 bits, k = 3 hashes
2  for i in 0..k-1: bits[(h1(key) + i*h2(key)) % m] = 1
3query(key):
4  for i in 0..k-1:
5    if bits[(h1(key) + i*h2(key)) % m] == 0: return DEFINITELY NOT PRESENT
6  return PROBABLY PRESENT                     # may be a false positive
7# expected false-positive rate = (1 - e^(-k*n/m))^k
Variables
m32
k3
keys inserted0
bits set0
fill0%
est. FP rate0.0%
Complexity
access —
search O(k)
insert O(k)
delete —
Speed