ZERO / HERO
A bouncer with a bad memory

Bloom Filters

The analogy

A bouncer cannot remember every face, so instead he remembers a few rough features of everyone who came in. If your features do not match, you definitely have not been here. If they do match, you probably have — but he might be confusing you with someone else. He is never wrong when he says no.

Visualizer

Bits, not items

step 1 / 10
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

16 bits, all zero. This filter will store NO items at all — only traces of them.m = 16 bits, k = 3 hashes

import hashlib

class Bloom:
    def __init__(self, m=1024, k=3):
        self.m, self.k = m, k
        self.bits = bytearray(m)

    def _hashes(self, item):
        h = hashlib.sha256(str(item).encode()).digest()
        return [int.from_bytes(h[i*4:(i+1)*4], "big") % self.m
                for i in range(self.k)]

    def add(self, item):
        for i in self._hashes(item):
            self.bits[i] = 1

    def __contains__(self, item):
        return all(self.bits[i] for i in self._hashes(item))
        # True  -> PROBABLY present
        # False -> DEFINITELY absent
Check yourself

A Bloom filter says an item is absent. How sure can you be?