Bloom Filter

用來快速搜尋資料是否存在於資料庫
我們的資料庫是一個 $2^m$ 大小的陣列

db = [False] * (2 ** m)

加資料進資料庫

我們有 $k$ 個 hash function 的輸出都是一個 $m$ bits 的數 ( $< 2^m$ )
把資料 $x$ 加進資料庫就是等於，將 $x$ 的各個雜湊值的位置設成 True

for i in range(k):
    db[hash[k](x)] = True

查詢資料 $x$ 是否在資料庫裡

if all([db[hash[k](x)] for i in range(k)]):
    # 資料 x 可能在資料庫裡
else:
    # 資料 x 一定不在資料庫裡