Topic
Bloom Filter
Learn Bloom Filter as a connected topic across chapters, concepts, simulations, and interview reasoning.
10 Concepts3 Articles46 min
Overview
Learn Bloom Filter as a connected topic across chapters, concepts, simulations, and interview reasoning.
How this topic helps
Algorithms
Data Structures
System Design
Caching
Learning Path in this Topic
Series that contain articles from Bloom Filter. Select a path to filter the article list.
Articles
3 matched articles
Article 1Bloom Filters Explained: Membership Testing with Zero False NegativesTLDR: A Bloom filter is a bit array of m bits + k independent hash functions that sets k bits on insert and checks those same k bits on lookup. If any checked bit is 0, the element is definitely not i19 minArticle 2Probabilistic Data Structures: A Practical Guide to Bloom Filters, HyperLogLog, and Count-Min SketchTLDR: Probabilistic data structures trade a small, bounded probability of being wrong for orders-of-magnitude better memory efficiency and O(1) speed. Bloom Filters answer "definitely not in this set"14 minArticle 3How Bloom Filters Work: The Probabilistic SetTLDR
TLDR: A Bloom Filter is a bit array + multiple hash functions that answers "Is X in the set?" in \(O(1)\) constant space. It can return false positives (say "yes" when the answer is "no") but ne13 min