Bloom Filter 與機率性資料結構

當你需要檢查一個元素是否在一個集合中，最簡單的方式是用 HashSet。但如果集合中有數十億個元素呢？HashSet 會佔用大量記憶體。

Bloom Filter 是一個極度節省記憶體的機率性資料結構。它可以告訴你：

• 一定不在（100% 正確）
• 可能在（有機率誤判）

這種取捨在許多大數據場景中非常值得——用微小的誤判率換取 90% 以上的記憶體節省。

實作 Bloom Filter

import math
import mmh3
from bitarray import bitarray

class BloomFilter:
    def __init__(self, n, fp_prob):
        """
        n: 預計插入的元素數量
        fp_prob: 期望的誤判率 (False Positive Probability)
        """
        self.fp_prob = fp_prob
        self.size = self._get_size(n, fp_prob)
        self.hash_count = self._get_hash_count(self.size, n)
        self.bit_array = bitarray(self.size)
        self.bit_array.setall(0)
    
    def _get_size(self, n, p):
        """計算需要的 bit 數"""
        m = -(n * math.log(p)) / (math.log(2) ** 2)
        return int(m)
    
    def _get_hash_count(self, m, n):
        """計算需要的 hash 函數數量"""
        k = (m / n) * math.log(2)
        return int(k)
    
    def add(self, item):
        """加入元素"""
        for i in range(self.hash_count):
            digest = mmh3.hash(item, i) % self.size
            self.bit_array[digest] = True
    
    def check(self, item):
        """檢查元素是否存在"""
        for i in range(self.hash_count):
            digest = mmh3.hash(item, i) % self.size
            if not self.bit_array[digest]:
                return False  # 一定不在
        return True  # 可能在

# 使用範例
bf = BloomFilter(1000000, 0.01)  # 100 萬個元素，1% 誤判率
print(f"bit 陣列大小: {bf.size/1024/1024:.2f} MB")
print(f"hash 函數數: {bf.hash_count}")

# 加入一些元素
for i in range(10000):
    bf.add(f"user_{i}_email@gmail.com")

# 測試
print(f"\n已存在的 email: {bf.check('user_123_email@gmail.com')}")
print(f"不存在的 email: {bf.check('fake_email@gmail.com')}")

# 測試誤判率
test_size = 10000
false_positives = 0
for i in range(test_size):
    if bf.check(f"not_in_set_{i}@test.com"):
        false_positives += 1
print(f"\n誤判率測試: {false_positives/test_size:.4%} (理論值: 1%)")

更多章節內容持續建置中...