Bloom filter是一種概率型數據結構，用于判斷某個元素是否屬于一個集合。它可以快速地檢索元素，而不需要存儲實際的元素本身，因此具有很小的存儲空間。
基本概念：
布隆過濾器使用一個位數組（bitmap）來表示集合，初始時所有位都被置為0。
通過多個哈希函數將元素映射到位數組的不同位置上，將對應位置的位設置為1。
當要查詢一個元素時，將該元素通過相同的哈希函數映射到位數組的相應位置，如果所有對應位置的位都為1，則表示該元素可能存在于集合中，否則一定不存在。
概率分析：
由于布隆過濾器使用多個哈希函數進行映射，因此可能會存在哈希沖突的情況。假設布隆過濾器中有n個元素，位數組的長度為m，使用k個哈希函數，則每個元素映射到位數組的位置的概率為1/m，因此一個位為0的位置的概率為(1-1/m)^kn。當查詢一個元素時，如果所有對應位置的位都為1，則表示該元素可能存在于集合中。但是有可能存在哈希沖突，導致其他元素也將對應位置的位置為1，因此存在一定的誤判率。
源碼分析：
以下是一個簡單的布隆過濾器的示例代碼：
from bitarray import bitarray
import mmh3
class BloomFilter:
def __init__(self, size, num_hashes):
self.size = size
self.num_hashes = num_hashes
self.bit_array = bitarray(size)
self.bit_array.setall(0)
def add(self, item):
for i in range(self.num_hashes):
index = mmh3.hash(item, i) % self.size
self.bit_array[index] = 1
def contains(self, item):
for i in range(self.num_hashes):
index = mmh3.hash(item, i) % self.size
if self.bit_array[index] == 0:
return False
return True
# 使用示例
bf = BloomFilter(1000000, 5)
bf.add("apple")
print(bf.contains("apple")) # 輸出True
print(bf.contains("banana")) # 輸出False
這段代碼使用了第三方庫bitarray和mmh3來實現布隆過濾器。bitarray用于表示位數組，mmh3用于計算哈希值。在初始化布隆過濾器時，需要指定位數組的長度和哈希函數的個數。add方法用于將元素添加到布隆過濾器中，contains方法用于判斷一個元素是否存在于布隆過濾器中。在查詢元素時，需要使用相同的哈希函數進行計算，并檢查對應位置的位是否為1。
