go语言中布隆过滤器低空间成本判断元素是否存在方式

第go语言中布隆过滤器低空间成本判断元素是否存在方式目录简介原理数据结构添加判断存在哈希函数布隆过滤器大小、哈希函数数量、误判率应用场景数据库黑名单实现数据结构初始化添加元素判断元素是否存在

简介

布隆过滤器（BloomFilter）是一种用于判断元素是否存在的方式，它的空间成本非常小，速度也很快。

但是由于它是基于概率的，因此它存在一定的误判率，它的Contains()操作如果返回true只是表示元素可能存在集合内，返回false则表示元素一定不存在集合内。因此适合用于能够容忍一定误判元素存在集合内的场景，比如缓存。

它一秒能够进行上百万次操作（主要取决于哈希函数的速度），并且1亿数据在误判率1%的情况下，只需要114MB内存。

原理

数据结构

布隆过滤器的数据结构是一个位向量，也就是一个由0、1所组成的向量（下面是一个初始向量）：

添加

每个元素添加进布隆过滤器前，都会经过多个不同的哈希函数，计算出不同的哈希值，然后映射到位向量上，也就是对应的位上面置1：

判断存在

判断元素是否存在也是如上图流程，根据哈希函数映射的位置，判断所有映射位置是否都为1，如果是则元素可能存在，否则元素一定不存在。

由于不同的值通过哈希函数之后可能会映射到相同的位置，因此如果一个不存在的元素对应的位位置都被其他元素所设置位1，则查询时就会误判：

假设上图元素3334并没有加入集合，但是由于它映射的位置已经被其他元素所映射，则查询时会误判。

哈希函数

布隆过滤器里面的哈希函数需要是彼此独立且均匀分布（类似于哈希表的哈希函数），而且需要尽可能的快，比如murmur3就是一个很好的选择。

布隆过滤器的性能严重依赖于哈希函数的性能，而一般哈希函数的性能则依赖于输入串（一般为字节数组）的长度，因此为了提高布隆过滤器的性能建议减少输入串的长度。

下面是一个简单的性能测试，单位是字节，可以看到时间的消耗随着元素的增大基本是线性增长的：

cpu:Intel(R)Core(TM)i5-10210UCPU@1.60GHz

BenchmarkAddAndContains/1-81805840659.6ns/op1.52MB/s0B/op0allocs/op

BenchmarkAddAndContains/2-81824064696.4ns/op2.87MB/s0B/op0allocs/op

BenchmarkAddAndContains/4-81819742649.5ns/op6.16MB/s0B/op0allocs/op

BenchmarkAddAndContains/8-81828371653.2ns/op12.25MB/s0B/op0allocs/op

BenchmarkAddAndContains/16-81828426642.0ns/op24.92MB/s0B/op0allocs/op

BenchmarkAddAndContains/32-82106834565.7ns/op56.57MB/s0B/op0allocs/op

BenchmarkAddAndContains/64-82063895579.3ns/op110.48MB/s0B/op0allocs/op

BenchmarkAddAndContains/128-81767673666.1ns/op192.17MB/s0B/op0allocs/op

BenchmarkAddAndContains/256-81292918916.9ns/op279.21MB/s0B/op0allocs/op

BenchmarkAddAndContains/512-87496661590ns/op322.11MB/s0B/op0allocs/op

BenchmarkAddAndContains/1024-83880152933ns/op349.12MB/s0B/op0allocs/op

BenchmarkAddAndContains/2048-82034045603ns/op365.51MB/s0B/op0allocs/op

BenchmarkAddAndContains/4096-810513411303ns/op362.38MB/s0B/op0allocs/op

BenchmarkAddAndContains/8192-85230522067ns/op371.23MB/s0B/op0allocs/op

布隆过滤器大小、哈希函数数量、误判率

布隆过滤器的大小、哈希函数数量和误判率之间是互相影响的，如果我们想减少误判率，则需要更大的布隆过滤器和更多的哈希函数。但是我们很难直观的计算出这些参数，还好有两个公式可以帮助我们计算出准确的数值：

在我们可以确定我们的元素数量和能够容忍的错误率的情况下，我们可以根据下面公式计算布隆过滤器大小和哈希函数数量：

n=元素数量

m=布隆过滤器大小（位数）

k=哈希函数数量

fpr=错误率（falsePositiveRate，假阳性率）

m=n*(-ln(fpr)/(ln2*ln2))

k=ln2*m/n

应用场景

数据库

布隆过滤器可以提前过滤所查询数据并不存在的请求，避免对磁盘访问的耗时。比如LevelDB就使用了布隆过滤器过滤请求/google/leve。

黑名单

假设有10亿个黑名单URL，每个URL大小为64字节。使用BloomFilter，如果错误率为0.1%，只需要1.4GB内存，如果错误率为0.0001%，也只需要2.9GB内存。

实现

这里简单的介绍一下Golang的实现方式。

代码：/jiaxwu/gomm

由于我们没办法直接申请一个bit组成的数组，因此我们使用uint64表示64个bit。

typeFilterstruct{

bits[]uint64//bit数组

bitsCntuint64//bit位数

hashs[]*hash.Hash//不同哈希函数

初始化

在初始化的时候，我们需要根据上面提到的两个公式，计算布隆过滤器的大小和哈希函数的数量。

//capacity：容量

//falsePositiveRate：误判率

funcNew(capacityuint64,falsePositiveRatefloat64)*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)

fori:=0;ihashsCnt;i++{

hashs[i]=hash.New()

returnamp;Filter{

bits:make([]uint64,(bitsCnt+63)/64),

bitsCnt:bitsCnt,

hashs:hashs,

添加元素

添加元素的时候，把每个哈希函数映射的位置都设置为1。这里需要注意，因为是用的uint64的数组，因此需要把按照bit计算的偏移，转换为按照64位计算的数组下标和对应下标元素里面的偏移。

//添加元素

func(f*Filter)Add(b[]byte){

for_,h:=rangef.hashs{

index,offset:=f.pos(h,b)

f.bits[index]|=1offset

//获取对应元素下标和偏移

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

returnindex,offset

判断元素是否存在

同理，只是这里我们如果发现某一位不为1则可以直接返回false。

//元素是否存在

//true表示可能存在

func(f*Filter)Contains(b[]byte)bool{

for_,h:=rangef.hashs{

index,offset:=