概要
Bloom Filter布隆过滤器用法。
- 如果被判断不是集合的,一定是真;
- 被判断为集合的,不一定是真;
- 不能删除数据;
1 | 做过一个工程数据记录 |
一点点数学
布隆过滤器的容量应该足够大以容纳你要存储的样本数据。在这种情况下,如果你有600万个比特币地址作为样本数据,你需要考虑以下几点来确定布隆过滤器的容量:
- 数据量大小: 600万个比特币地址。
- 错误率: 你需要考虑你可以接受的误判率。通常,误判率越低,需要的内存就越多。在你的应用中,选择一个合理的误判率,通常是根据应用场景和性能要求来决定的。
布隆过滤器的容量应该足够大,以至于填充600万个比特币地址后,误判率仍然可以保持在可接受的范围内。但具体需要多大的容量取决于所选的误判率。你可以使用布隆过滤器的理论公式来估算所需的位数组大小。
具体计算公式如下:
$m = -\frac{n \ln p}{(\ln 2)^2}$
其中:
- ( m ) 是位数组的大小(容量)。
- ( n ) 是预期要插入的元素数量,即比特币地址的数量。
- ( p ) 是所需的误判率。
在这个例子中,( n = 600万 ),( p ) 是你选择的误判率。假设你选择了一个相对较小的误判率,比如0.001(或0.1%),那么你可以将 ( p = 0.001 ) 带入计算公式。
$m = -\frac{6000000 \times \ln(0.001)}{(\ln 2)^2}$
计算出 ( m ) 后,你会得到所需的位数组大小(容量),你可以将其用作布隆过滤器的初始化参数之一。
需要注意的是,这个计算只是一个估算,实际应用中可能需要根据实际情况进行调整。如果内存资源允许,可以选择更大的容量以减小误判率。
工程实践
1 | package main |