簡介
布隆過濾器（BloomFilter）是一種用于判斷元素是否存在的方式，它的空間成本非常小，速度也很快。
但是由于它是基于概率的，因此它存在一定的誤判率，它的Contains()操作如果返回true只是表示元素可能存在集合內，返回false則表示元素一定不存在集合內。因此適合用于能夠容忍一定誤判元素存在集合內的場景，比如緩存。
它一秒能夠進行上百萬次操作（主要取決于哈希函數的速度），并且1億數據在誤判率1%的情況下，只需要114MB內存。
原理
數據結構
布隆過濾器的數據結構是一個位向量，也就是一個由0、1所組成的向量（下面是一個初始向量）：
添加
每個元素添加進布隆過濾器前，都會經過多個不同的哈希函數，計算出不同的哈希值，然后映射到位向量上，也就是對應的位上面置1：
判斷存在
判斷元素是否存在也是如上圖流程，根據哈希函數映射的位置，判斷所有映射位置是否都為1，如果是則元素可能存在，否則元素一定不存在。
由于不同的值通過哈希函數之后可能會映射到相同的位置，因此如果一個不存在的元素對應地位位置都被其他元素所設置位1，則查詢時就會誤判：
假設上圖元素3334并沒有加入集合，但是由于它映射的位置已經被其他元素所映射，則查詢時會誤判。
哈希函數
布隆過濾器里面的哈希函數需要是彼此獨立且均勻分布（類似于哈希表的哈希函數），而且需要盡可能的快，比如murmur3就是一個很好的選擇。
布隆過濾器的性能嚴重依賴于哈希函數的性能，而一般哈希函數的性能則依賴于輸入串（一般為字節數組）的長度，因此為了提高布隆過濾器的性能建議減少輸入串的長度。
下面是一個簡單的性能測試，單位是字節，可以看到時間的消耗隨著元素的增大基本是線性增長的：
cpu: Intel(R) Core(TM) i5-10210U CPU @ 1.60GHz
BenchmarkAddAndContains/1-8 1805840 659.6 ns/op 1.52 MB/s 0 B/op 0 allocs/op
BenchmarkAddAndContains/2-8 1824064 696.4 ns/op 2.87 MB/s 0 B/op 0 allocs/op
BenchmarkAddAndContains/4-8 1819742 649.5 ns/op 6.16 MB/s 0 B/op 0 allocs/op
BenchmarkAddAndContains/8-8 1828371 653.2 ns/op 12.25 MB/s 0 B/op 0 allocs/op
BenchmarkAddAndContains/16-8 1828426 642.0 ns/op 24.92 MB/s 0 B/op 0 allocs/op
BenchmarkAddAndContains/32-8 2106834 565.7 ns/op 56.57 MB/s 0 B/op 0 allocs/op
BenchmarkAddAndContains/64-8 2063895 579.3 ns/op 110.48 MB/s 0 B/op 0 allocs/op
BenchmarkAddAndContains/128-8 1767673 666.1 ns/op 192.17 MB/s 0 B/op 0 allocs/op
BenchmarkAddAndContains/256-8 1292918 916.9 ns/op 279.21 MB/s 0 B/op 0 allocs/op
BenchmarkAddAndContains/512-8 749666 1590 ns/op 322.11 MB/s 0 B/op 0 allocs/op
BenchmarkAddAndContains/1024-8 388015 2933 ns/op 349.12 MB/s 0 B/op 0 allocs/op
BenchmarkAddAndContains/2048-8 203404 5603 ns/op 365.51 MB/s 0 B/op 0 allocs/op
BenchmarkAddAndContains/4096-8 105134 11303 ns/op 362.38 MB/s 0 B/op 0 allocs/op
BenchmarkAddAndContains/8192-8 52305 22067 ns/op 371.23 MB/s 0 B/op 0 allocs/op
復制代碼
布隆過濾器大小、哈希函數數量、誤判率
布隆過濾器的大小、哈希函數數量和誤判率之間是互相影響的，如果我們想減少誤判率，則需要更大的布隆過濾器和更多的哈希函數。但是我們很難直觀地計算出這些參數，還好有兩個公式可以幫助我們計算出準確的數值：
在我們可以確定我們的元素數量和能夠容忍的錯誤率的情況下，我們可以根據下面公式計算布隆過濾器大小和哈希函數數量：
n = 元素數量
m = 布隆過濾器大小（位數）
k = 哈希函數數量
fpr = 錯誤率（falsePositiveRate，假陽性率）
m = n*(-ln(fpr)/(ln2*ln2))
k = ln2 * m / n
復制代碼
應用場景
數據庫
布隆過濾器可以提前過濾所查詢數據并不存在的請求，避免對磁盤訪問的耗時。比如LevelDB就使用了布隆過濾器過濾請求github.com/google/leve… 。
黑名單
假設有10億個黑名單URL，每個URL大小為64字節。使用Bloom Filter，如果錯誤率為0.1%，只需要1.4GB內存，如果錯誤率為0.0001%，也只需要2.9GB內存。
實現
這里簡單的介紹一下Golang的實現方式。
代碼：github.com/jiaxwu/gomm…
數據結構
由于我們沒辦法直接申請一個bit組成的數組，因此我們使用uint64表示64個bit。
type Filter struct {
bits []uint64 // bit數組
bitsCnt uint64 // bit位數
hashs []*hash.Hash // 不同哈希函數
}
復制代碼
初始化
在初始化的時候，我們需要根據上面提到的兩個公式，計算布隆過濾器的大小和哈希函數的數量。
// capacity：容量
// falsePositiveRate：誤判率
func New(capacity uint64, falsePositiveRate float64) *Filter {
// bit數量
ln2 := math.Log(2.0)
factor := -math.Log(falsePositiveRate) / (ln2 * ln2)
bitsCnt := mmath.Max(1, uint64(float64(capacity)*factor))
// 哈希函數數量
hashsCnt := mmath.Max(1, int(ln2*float64(bitsCnt)/float64(capacity)))
hashs := make([]*hash.Hash, hashsCnt)
for i := 0; i < hashsCnt; i++ {
hashs[i] = hash.New()
}
return &Filter{
bits: make([]uint64, (bitsCnt+63)/64),
bitsCnt: bitsCnt,
hashs: hashs,
}
}
復制代碼
添加元素
添加元素的時候，把每個哈希函數映射的位置都設置為1。這里需要注意，因為是用的uint64的數組，因此需要把按照bit計算的偏移，轉換為按照64位計算的數組下標和對應下標元素里面的偏移。
// 添加元素
func (f *Filter) Add(b []byte) {
for _, h := range f.hashs {
index, offset := f.pos(h, b)
f.bits[index] |= 1 << offset
}
}
// 獲取對應元素下標和偏移
func (f *Filter) pos(h *hash.Hash, b []byte) (uint64, uint64) {
hashValue := h.Sum64(b)
// 按照位計算的偏移
bitsIndex := hashValue % f.bitsCnt
// 因為一個元素64位，因此需要轉換
index := bitsIndex / uint64Bits
// 在一個元素里面的偏移
offset := bitsIndex % uint64Bits
return index, offset
}
復制代碼
判斷元素是否存在
同理，只是這里我們如果發現某一位不為1則可以直接返回false。
// 元素是否存在
// true表示可能存在
func (f *Filter) Contains(b []byte) bool {
for _, h := range f.hashs {
index, offset := f.pos(h, b)
mask := uint64(1) << offset
// 判斷這一位是否位1
if (f.bits[index] & mask) != mask {
return false
}
}
return true
}
