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

Memory

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

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

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

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

布隆过滤器是通过khash函数将某个key映射到m个的比特位上。那么某个key的比特位有可能会被其他的一个或多个key占用,即会产生误判为存在的情况,所以这个误判率取决于…