Overview
A Bloom Filter uses a bit array and multiple independent hash functions to represent a set approximately. When an element is inserted, the hash functions identify several bit positions, and those positions are set to 1. During a membership query, the filter checks the same positions to determine whether the element may be present.
How it works
Create a bit array containing m bits, initially set to 0.; Choose k hash functions that map elements to positions in the bit array.; To insert an element, calculate its k hash positions.; Set every corresponding bit to 1.; To check membership, calculate the same k positions.; If any required bit is 0, the element is definitely not present.
Key concepts
Bit arrays; Hash functions; Probabilistic membership testing; False positives; False negatives; False-positive probability
Time complexity
operation: Insertion; complexity: O(k); operation: Membership Query; complexity: O(k)
Space complexity
O(m) bits, where m is the number of bits in the filter.
Example
description: Suppose a Bloom Filter uses a bit array and three hash functions.; insertedElement: apple; insertOperation: Hash function 1 identifies position 2.; Hash function 2 identifies position 5.; membershipCheck: caseOne: If a required bit is 0, the queried element is definitely absent.; caseTwo: If all required bits are 1, the element may be present because other elements could have set the same bits.
Applications
Database query optimization; Web caching; Checking whether URLs may have been visited; Distributed systems; Network packet processing; Duplicate detection