Probabilistic Data Structures TODO
Concept
Probabilistic data structures trade an exact answer for a bounded error, in exchange for a large reduction in memory. A Bloom filter tests set membership using a bit array and k hash functions; it can produce false positives but never false negatives, and doesn't support deletion. A Cuckoo filter instead stores a short fingerprint of the element in one of two candidate buckets, which lets it support deletion. A Count-Min sketch estimates frequencies using a grid of counters indexed by several hash rows; collisions can cause it to overestimate, but never underestimate. HyperLogLog estimates the cardinality (count of distinct elements) by recording, across many buckets, the maximum number of leading zero bits seen in a hash value — using almost constant memory.
In places like logs, mempools, or caches where the element count runs into the hundreds of millions, holding an exact set or counter blows the memory budget before anything else fails.
Code & Formula
# Day 6: 확률적 자료구조 — Bloom Filter로 집합 포함 여부를 확률적으로 판정
# 비트 배열 + k개의 해시로 원소를 삽입하고, 거짓 양성(false positive)이 실제로 발생함을 확인한다.
import hashlib
class BloomFilter:
def __init__(self, size, k):
self.size = size
self.k = k
self.bits = [0] * size
def _hashes(self, item):
for i in range(self.k):
h = hashlib.sha256(f"{i}:{item}".encode()).digest()
yield int.from_bytes(h, "big") % self.size
def add(self, item):
for idx in self._hashes(item):
self.bits[idx] = 1
def might_contain(self, item):
return all(self.bits[idx] for idx in self._hashes(item))
bf = BloomFilter(size=64, k=3)
inserted = [f"tx-{i}" for i in range(20)]
for item in inserted:
bf.add(item)
checked, false_positives = 2000, 0
for i in range(checked):
probe = f"probe-{i}"
if probe not in inserted and bf.might_contain(probe):
false_positives += 1
print(f"삽입 원소 {len(inserted)}개, 비트 배열 크기 {bf.size}, 해시 개수 {bf.k}")
print(f"might_contain('tx-5') = {bf.might_contain('tx-5')} (실제 포함 원소 -> 항상 True)")
print(f"거짓 양성 {false_positives} / {checked}회 (비율 {false_positives / checked:.3%})")
docs/code/algorithms/algorithms-6.py
Exercise
Implement a Bloom filter and, by varying the bit count m and the number of hash functions k, compare the measured false-positive rate against the theoretical value.
Practical Connection
Bloom-style filters are used in P2P gossip to avoid re-propagating transaction or block hashes that have already been seen, and Verex could apply the same idea as a cheap first-pass filter for event logs or order IDs it has already processed.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.