布隆过滤器与设计

布隆过滤器与设计

简介

在计算机中集合是用哈希表(hash table)来存储的。它的好处是快速准确,缺点是费存储空间。当集合比较小时,这个问题不显着,但是当集合巨大时,哈希表存储效率低的问题就显现出来了。
所以我们可以使用布隆过滤器来过滤掉解决这个问题
布隆过滤器像是一个可以复用基础元素的hash table 通过容忍误判来减少了空间的使用量

原理

,当一个元素被加入集合时,通过K个 散列函数 将这个元素映射成一个位 数组 中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。
布隆过滤器由长度为MBit数组组成 如下图所示

当要把一个新元素加入到过滤器中的时候
我们使用K个不同的Hash函数 并把返回的索引对应的位设置为1
如下图所示

当我们要查询的时候 只需要把要查询的数据同样通过k个hash函数进行运算
查看返回的hash的函数位数是否都为1

  • 如果都为1 那么就是可能存在
  • 如果有0 那么就是一定不存在

设计

在整个布隆过滤器中
最关键的两个数据就是hash函数的数量 K 和 过滤器的长度M
如果 M 过小那么误报率就会变得很高 所以我们可以根据误报率来决定M的长度
如果 K 过多就会让整个过滤器变得很慢 如果K过少 那么误报率也会上升

通过上图可以看出 增加散列函数k的数量将大大降低错误率p

我们可以根据过滤器的大小m,散列函数的数量k,和插入的元素数n来计算误差率p,公式如下:
如果我们自己设置 p 和 n
那么可以使用以下公式来计算