Back
+30 XP
Concept

Bloom Filter with Multiple Hashing Functions

Hitting disk or network backends to check if a non-existent key exists destroys database throughput. A Bloom Filter uses a compact bit array and $K$ hash functions. It guarantees zero false negatives: if it returns `False`, the key is definitely absent from disk πŸŒΈπŸ”βš‘.

python
import hashlib

class MiniBloom:
    def __init__(self, size=64):
        self.size = size
        self.bits = [0] * size

    def add(self, key):
        h1 = int(hashlib.md5(key.encode()).hexdigest(), 16) % self.size
        self.bits[h1] = 1

    def check(self, key):
        h1 = int(hashlib.md5(key.encode()).hexdigest(), 16) % self.size
        return self.bits[h1] == 1

bf = MiniBloom()
bf.add("session_xyz")
print("Contains session_xyz:", bf.check("session_xyz"))

# 28. Bloom Filter with Multiple Hashing Functions In LSM-Tree databases (like RocksDB, Cassandra, and Bigtable), querying for a key that does not exist is the most expensive operation: the database searches the MemTable, scans SSTable index blocks, and reads multiple disk pages only to find nothing πŸ›‘. ```python # The Bloom Filter Shield: # [Query: "user:999"] # | # v # [In-Memory Bloom Filter] # | # +---> False: "Definite Miss!" -> RETURN NONE IN 0.001ms (Zero Disk I/O!) # | # +---> True: "Probable Hit" -> Check SSTable on Disk (1% false positive risk) ``` ### The $K$-Hash Bitmask Principle - **Adding an item**: Compute $K$ independent hash indices across the bit vector and set all $K$ bits to `1`. - **Querying an item**: Check if all $K$ bits are `1`. If even a single bit is `0`, the item was **NEVER** added to the set. - **Space Efficiency**: Requires approximately ~10 bits per item to achieve a 1% false positive rateβ€”storing millions of items in a few megabytes of RAM πŸŒΈπŸ”βš‘! --- ### Interactive Pop-Quiz 🧠 #### What is the fundamental probabilistic guarantee of a Bloom Filter? - [ ] It has ZERO false negatives (if it says an element is absent, it is 100% guaranteed to be absent from the database) 🌸 - [ ] It has zero false positives - [ ] It compresses data losslessly using LZW - [ ] It encrypts stored keys using AES --- ### Practical Challenge 🎯 Implement `BloomFilter(size_bits: int = 128, num_hashes: int = 3)` with `bit_array: list[int]`. Provide `_hashes(key: str) -> list[int]` deriving $K$ offsets via `(h1 + i * h2) % size_bits` (using MD5 and SHA-256), `add(key: str)`, and `might_contain(key: str) -> bool`. Add `'user_101'` and `'user_202'`. Verify both return `True` and an unadded key returns `False`. Print results. <details> <summary>Solution</summary> ```python import hashlib class BloomFilter: def __init__(self, size_bits: int = 128, num_hashes: int = 3): self.size_bits = size_bits self.num_hashes = num_hashes self.bit_array = [0] * size_bits def _hashes(self, key: str) -> list[int]: h1 = int(hashlib.md5(key.encode()).hexdigest(), 16) h2 = int(hashlib.sha256(key.encode()).hexdigest(), 16) return [(h1 + i * h2) % self.size_bits for i in range(self.num_hashes)] def add(self, key: str): for bit_idx in self._hashes(key): self.bit_array[bit_idx] = 1 def might_contain(self, key: str) -> bool: for bit_idx in self._hashes(key): if self.bit_array[bit_idx] == 0: return False return True bf = BloomFilter(size_bits=128, num_hashes=3) bf.add("user_101") bf.add("user_202") assert bf.might_contain("user_101") is True assert bf.might_contain("user_202") is True assert bf.might_contain("unknown_ghost_user") is False print("BloomFilter verified: Zero false negatives, membership checks accurate") ``` </details>

Checkpoint

What is the fundamental probabilistic guarantee of a Bloom Filter? 🧠

Practice

Implement `BloomFilter(size_bits: int = 128, num_hashes: int = 3)` with `bit_array: list[int]`. Provide `_hashes(key: str) -> list[int]` deriving $K$ offsets via `(h1 + i * h2) % size_bits` (using MD5 and SHA-256), `add(key: str)`, and `might_contain(key: str) -> bool`. Add `'user_101'` and `'user_202'`. Verify both return `True` and an unadded key returns `False`. Print results. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks