Bloom Filter 使用很短的二进制向量，通过牺牲准确率获得了极高的空间利用率。在大规模数据查询场景下，能有效避免磁盘 IO，具有很高地查询效率。

Bloom Filter 和 Bitmap 有所类似，都是利用二进制向量和映射函数判断元素是否存在。不同的是，Bitmap 只有一个映射函数，向量大小不能小于最大的整数；Bloom Filter 具有多个映射函数，根据不同要求的误判率场景，可以选择不同大小的二进制向量。

## 2. 常见的应用场景

Bloom Filter 具有一定的误判率，主要解决一定不存在和可能存在两类问题。

### 2.2 可能存在 – True

Web 拦截器。拦截在黑名单中的 URL 地址

## 3. 布隆过滤的参数选择

`k = (m/n) ln2`

m 是二进制向量的大小
n 是元素的数量
k 是映射函数的个数
ln2 是常数，约等于 0.69

m/nkk=1k=2k=3k=4k=5k=6k=7k=8
21.390.3930.400
32.080.2830.2370.253
42.770.2210.1550.1470.160
53.460.1810.1090.0920.0920.101
64.160.1540.08040.06090.05610.05780.0638
74.850.1330.06180.04230.03590.03470.0364
85.550.1180.04890.03060.0240.02170.02160.0229
96.240.1050.03970.02280.01660.01410.01330.01350.0145
106.930.09520.03290.01740.01180.009430.008440.008190.00846
117.620.08690.02760.01360.008640.00650.005520.005130.00509
128.320.080.02360.01080.006460.004590.003710.003290.00314
139.010.0740.02030.008750.004920.003320.002550.002170.00199
149.70.06890.01770.007180.003810.002440.001790.001460.00129
1510.40.06450.01560.005960.0030.001830.001280.0010.000852
1611.10.06060.01380.0050.002390.001390.0009350.0007020.000574
1711.80.05710.01230.004230.001930.001070.0006920.0004990.000394
1812.50.0540.01110.003620.001580.0008390.0005190.000360.000275
1913.20.05130.009980.003120.00130.0006630.0003940.0002640.000194
2013.90.04880.009060.00270.001080.000530.0003030.0001960.00014
2114.60.04650.008250.002360.0009050.0004270.0002360.0001470.000101
2215.20.04440.007550.002070.0007640.0003470.0001850.0001127.46e-05
2315.90.04250.006940.001830.0006490.0002850.0001478.56e-055.55e-05
2416.60.04080.006390.001620.0005550.0002350.0001176.63e-054.17e-05
2517.30.03920.005910.001450.0004780.0001969.44e-055.18e-053.16e-05
26180.03770.005480.001290.0004130.0001647.66e-054.08e-052.42e-05
2718.70.03640.00510.001160.0003590.0001386.26e-053.24e-051.87e-05
2819.40.03510.004750.001050.0003140.0001175.15e-052.59e-051.46e-05
2920.10.03390.004440.0009490.0002769.96e-054.26e-052.09e-051.14e-05
3020.80.03280.004160.0008620.0002438.53e-053.55e-051.69e-059.01e-06
3121.50.03170.00390.0007850.0002157.33e-052.97e-051.38e-057.16e-06
3222.20.03080.003670.0007170.0001916.33e-052.5e-051.13e-055.73e-06

`m = (k * n) / ln2`

10e6 bit = 704.6 KB 。

## 4. 布隆过滤的缺点

1. 无法删除元素。因为一个二进制向量位，可能对应多个元素的映射，不能直接将其置 0 。

1. 只适用于单机系统，内存开销随数据规模成线性关系。目前已经有一些中间件提供了布隆过滤，比如 Redis ，可以用于超大规模数据的场景。

Spectral Bloom Filters

D-left 计算布隆过滤（D-left Counting Bloom Filters）

Dynamic Counting Filters

## 5. Go 语言实现

，对 Bloom Filter 进行简单测试。

```package main
import (
"fmt"
"github.com/willf/bloom"
)
func main() {
n := uint(10000)
error_rate := 0.003
need_m, need_k := bloom.EstimateParameters(n, error_rate)
fmt.Printf("Set m = %d , k = %d \n", need_m, need_k)
filter := bloom.New(need_m, need_k)
for i := 0; i < int(n); i++ {
}
fmt.Println(filter.Test([]byte(fmt.Sprintf("https://www.chenshaowen.com/%d", 10000))))
fmt.Printf("Done")
}```

```Set m = 120910 , k = 9
false
Done```