Probabilistic data structures accept a small chance of error in exchange for dramatic memory savings. A Bloom filter uses 10 bits per element to achieve under a 1% false positive rate — compared to storing actual keys. This article covers the three most important probabilistic structures: Bloom filters, Count-Min Sketch, and HyperLogLog.
Bloom Filters: Membership Without Storage
A Bloom filter is a bit array with k hash functions. To add an element, set k bits. To query, check if all k bits are set:
import mmh3
from bitarray import bitarray
class BloomFilter:
def __init__(self, size: int, num_hashes: int):
self.size = size
self.num_hashes = num_hashes
self.bit_array = bitarray(size)
self.bit_array.setall(0)
def add(self, item: str):
for i in range(self.num_hashes):
idx = mmh3.hash(item, i) % self.size
self.bit_array[idx] = 1
def __contains__(self, item: str) -> bool:
for i in range(self.num_hashes):
idx = mmh3.hash(item, i) % self.size
if not self.bit_array[idx]:
return False # definitely not in set
return True # probably in set (may be false positive)
# 1 million items, 1% false positive rate:
# Required bits: ~9.6 million (~1.2 MB)
# vs storing 1 million strings: ~50+ MBOptimal Hash Function Count
def optimal_bloom_params(n: int, fp_rate: float) -> tuple:
"""Calculate optimal bit array size and hash count."""
import math
m = -n * math.log(fp_rate) / (math.log(2) ** 2)
k = (m / n) * math.log(2)
return int(m), int(k)
# n = 1_000_000 items, fp_rate = 0.01 (1%):
# m = 9,585,058 bits (~1.14 MB)
# k = 7 hash functionsdef bloom_filter_fp_rate(n: int, m: int, k: int) -> float:
"""Calculate false positive rate for given parameters."""
import math
return (1 - math.exp(-k * n / m)) ** k
# Verification:
# n=1M, m=9585058, k=7 → fp_rate ≈ 0.01 ✓Count-Min Sketch: Frequency Estimation
Count-Min Sketch estimates event frequencies in a stream using a 2D array of counters:
import mmh3
class CountMinSketch:
def __init__(self, width: int, depth: int):
self.width = width
self.depth = depth
self.table = [[0] * width for _ in range(depth)]
self.hashes = [(lambda x, i=i: mmh3.hash(x, i) % width) for i in range(depth)]
def update(self, item: str, count: int = 1):
for i in range(self.depth):
self.table[i][self.hashes[i](item)] += count
def query(self, item: str) -> int:
return min(self.table[i][self.hashes[i](item)] for i in range(self.depth))
def __contains__(self, item: str) -> bool:
return self.query(item) > 0
# Width = ceil(e / epsilon), Depth = ceil(ln(1/delta))
# For epsilon=0.001, delta=0.01: width=2718, depth=5
# Memory: 2718 × 5 × 8 bytes ≈ 109 KB for streaming frequency estimationHyperLogLog: Cardinality Estimation
HyperLogLog estimates the number of distinct elements in a stream using O(1) memory:
import mmh3
import math
class HyperLogLog:
def __init__(self, precision: int = 14):
"""precision p: 2^p registers, standard error ≈ 1.04 / sqrt(2^p)."""
self.p = precision
self.m = 1 << precision
self.registers = [0] * self.m
def add(self, item: str):
h = mmh3.hash(item, 0)
idx = h & ((1 << self.p) - 1) # first p bits → register index
w = h >> self.p # remaining bits → leading zeros
zeros = self._count_leading_zeros(w)
self.registers[idx] = max(self.registers[idx], zeros)
def _count_leading_zeros(self, x: int) -> int:
if x == 0:
return 32
count = 0
for i in range(31, -1, -1):
if x & (1 << i):
break
count += 1
return count + 1
def cardinality(self) -> float:
alpha = 0.7213 / (1 + 1.079 / self.m)
raw = alpha * self.m * (2 ** (sum(self.registers) / self.m))
if raw <= 2.5 * self.m:
zeros = self.registers.count(0)
if zeros > 0:
return self.m * math.log(self.m / zeros)
return raw
# HyperLogLog with 2^14 = 16384 registers:
# Memory: 16 KB
# Standard error: 0.81%
# Can estimate cardinality up to ~2^64 distinct elementstradeoff / Exact vs Probabilistic Counting
Probabilistic data structures are not approximations — they are the correct tool for problems where exact answers require more memory than available, or where approximate answers are sufficient for decision-making.
For counting distinct users, unique page views, or cardinality of large sets, HyperLogLog is the industry standard. Redis implements HyperLogLog as a native data type. Twitter uses it for tweet engagement metrics.
Synthesis
Bloom filters check membership in O(1) with minimal memory. Count-Min Sketch estimates frequencies in streaming data. HyperLogLog counts distinct elements with constant memory. These probabilistic structures are the foundation of modern real-time analytics, network monitoring, and distributed systems where exact counting is impractical.