江苏龙网

  1. 主页 > 生活百科 > >

布隆过滤器：一种低空间成本的判断元素是否存在的方式

布隆过滤器

简介布隆过滤器（BloomFilter）是一种用于判断元素是否存在的方式，它的空间成本非常小，速度也很快 。
但是由于它是基于概率的，因此它存在一定的误判率，它的Contains()操作如果返回true只是表示元素可能存在集合内，返回false则表示元素一定不存在集合内 。因此适合用于能够容忍一定误判元素存在集合内的场景，比如缓存 。
它一秒能够进行上百万次操作（主要取决于哈希函数的速度），并且1亿数据在误判率1%的情况下，只需要114MB内存 。
原理数据结构布隆过滤器的数据结构是一个位向量，也就是一个由0、1所组成的向量（下面是一个初始向量）：

布隆过滤器：一种低空间成本的判断元素是否存在的方式

文章插图
 
添加每个元素添加进布隆过滤器前，都会经过多个不同的哈希函数，计算出不同的哈希值，然后映射到位向量上，也就是对应的位上面置1：
布隆过滤器：一种低空间成本的判断元素是否存在的方式

文章插图
 
判断存在判断元素是否存在也是如上图流程，根据哈希函数映射的位置，判断所有映射位置是否都为1，如果是则元素可能存在，否则元素一定不存在 。
由于不同的值通过哈希函数之后可能会映射到相同的位置，因此如果一个不存在的元素对应地位位置都被其他元素所设置位1，则查询时就会误判：
布隆过滤器：一种低空间成本的判断元素是否存在的方式

文章插图
 
假设上图元素3334并没有加入集合，但是由于它映射的位置已经被其他元素所映射，则查询时会误判 。
哈希函数布隆过滤器里面的哈希函数需要是彼此独立且均匀分布（类似于哈希表的哈希函数），而且需要尽可能的快，比如murmur3就是一个很好的选择 。
布隆过滤器的性能严重依赖于哈希函数的性能，而一般哈希函数的性能则依赖于输入串（一般为字节数组）的长度，因此为了提高布隆过滤器的性能建议减少输入串的长度 。
下面是一个简单的性能测试，单位是字节，可以看到时间的消耗随着元素的增大基本是线性增长的：
cpu: Intel(R) Core(TM) i5-10210U CPU @ 1.60GHzBenchmarkAddAndContains/1-81805840659.6 ns/op1.52 MB/s0 B/op0 allocs/opBenchmarkAddAndContains/2-81824064696.4 ns/op2.87 MB/s0 B/op0 allocs/opBenchmarkAddAndContains/4-81819742649.5 ns/op6.16 MB/s0 B/op0 allocs/opBenchmarkAddAndContains/8-81828371653.2 ns/op12.25 MB/s0 B/op0 allocs/opBenchmarkAddAndContains/16-81828426642.0 ns/op24.92 MB/s0 B/op0 allocs/opBenchmarkAddAndContains/32-82106834565.7 ns/op56.57 MB/s0 B/op0 allocs/opBenchmarkAddAndContains/64-82063895579.3 ns/op110.48 MB/s0 B/op0 allocs/opBenchmarkAddAndContains/128-81767673666.1 ns/op192.17 MB/s0 B/op0 allocs/opBenchmarkAddAndContains/256-81292918916.9 ns/op279.21 MB/s0 B/op0 allocs/opBenchmarkAddAndContains/512-87496661590 ns/op322.11 MB/s0 B/op0 allocs/opBenchmarkAddAndContains/1024-83880152933 ns/op349.12 MB/s0 B/op0 allocs/opBenchmarkAddAndContains/2048-82034045603 ns/op365.51 MB/s0 B/op0 allocs/opBenchmarkAddAndContains/4096-810513411303 ns/op362.38 MB/s0 B/op0 allocs/opBenchmarkAddAndContains/8192-85230522067 ns/op371.23 MB/s0 B/op0 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 // 不同哈希函数}复制代码初始化在初始化的时候，我们需要根据上面提到的两个公式，计算布隆过滤器的大小和哈希函数的数量 。


推荐阅读


上一篇：三四十岁的大龄程序员，到底该怎么做才能避免失业？

下一篇：element乘风破浪