• 展开微博窗口
  • QQ:52619941
  • 微信:cnmemory
  • 展开分类目录
  • 还没有账号?

Memory

对布隆过滤器(Bloom Filter)一点总结

布隆过滤器是一种空间利用率高,可以用来对数据进行排重过滤处理的数据结构,具有以下两点特征:

  • 判定为不存在的数据一定不存在
  • 判定为存在的数据可能存在也可能不存在

存在的数据如果实际上并不存在,称为false positive,那么为什么会有这种现象呢?

布隆过滤器是通过khash函数将某个key映射到m个的比特位上。那么某个key的比特位有可能会被其他的一个或多个key占用,即会产生误判为存在的情况,所以这个误判率取决于k(hash函数个数)、m(比特位个数)、n(元素个数),关于误差率推导,由于我的数学比较不好,还没领悟透彻,可以参考网络上其他文章。

因为比特位非01,且多个key共享比特位,也导致了布隆过滤器无法删除已添加的元素,因为删除某个key会影响到其他key

当然还有一些其他变种的布隆过滤器使得可以删除元素,例如将比特位变成一个计数器,删除元素时只需要将计数器-1即可。

码字很辛苦,转载请注明来自雨林寒舍《对布隆过滤器(Bloom Filter)一点总结》

评论