Bloom Filter

Probabilistic set membership with space efficiency.

5 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

Bloom Filter Concept

Bloom Filter is a space-efficient probabilistic data structure for set membership. Uses bit array of m bits and k hash functions. Insert: set k bits. Query: check all k bits. False positives possible (bits set by other elements), false negatives impossible.

Operations

Gobloom-filter-implementation.go

34 linesLn 1, Col 1Go

Bit array of size m, k hash functions. Add: set k bits. Contains: check all k bits. Optimal k ≈ (m/n) * ln(2). False positive rate ≈ (1 - e^(-kn/m))^k.

Hash Functions

Need k independent hash functions. Practical approaches: (1) Use different seeds for same hash (MurmurHash, FNV). (2) Double hashing: h1, h2, then h_i = h1 + i*h2. (3) Cryptographic hashes with different prefixes.

Tradeoffs

Pros	Cons
Space efficient (bits per element)	False positives possible
O(k) insert/query	Cannot delete (counting bloom filter needed)
No false negatives	Cannot enumerate elements
Parallelizable	Tuning m, k for target FPR

Web caching: Check if URL might be in cache before disk lookup.
Database: Avoid disk reads for non-existent rows.
Distributed systems: Membership queries in large clusters.
Spam filtering: Check if email hash in spam set.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.