caching

Bloom Filter

Space-efficient probabilistic set membership — may have false positives, never false negatives

Filter Size32 bits
Hash Functions3
Items Added0
Fill Rate0%
FP Probability~0.0%
// bit array (0/32 bits set)
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

// event log

No events yet.

// how it works

  • k hash functions map each item to k bit positions
  • ADD: set all k bits to 1
  • QUERY: check if all k bits are 1
  • If any bit is 0 → DEFINITELY not in set
  • If all bits 1 → MAYBE in set (could be collision)

// trade-offs

  • Extremely space-efficient vs hash sets
  • O(k) add and query, k = number of hashes
  • Used in databases, CDNs, spell checkers
  • Cannot delete items (use Counting Bloom Filter)
  • FP rate grows as filter fills up