Bloom Filters

Core concept: a Bloom filter is a probabilistic set membership structure. It uses a bit array of m = 24 slots, all starting at 0, plus k = 3 independent hash functions.

INSERT: for the key "apple", the three hash functions produce positions 2, 7 and 19. Set bits at positions {2, 7, 19} to 1. EXACTLY three cells of the 24 are filled -- cell 2, cell 7 and cell 19 -- and every other cell stays 0. Draw exactly three call-out arrows, one per filled cell.

LOOKUP: hash the query key and read those same three cells. Any zero proves the key was never inserted. All ones only SUGGEST presence -- a false positive is possible because other keys may have set the same bits.

Depict: one horizontal 24-cell bit array with 0-based index labels 0..23 beneath it, the three hash functions on the left, and a short caption naming the set {2, 7, 19}.