[算法]检查元素存在于集合-Bloom Filter/Counting Bloom Filter算法简介


判断某个元素是否在集合中是开发中常见的一个问题。如果数据集合比较小常用的查找、遍历,数据库查询等方式还可用,但是在缓存是否命中这种效率敏感的高频调用或者爬虫目标URL判重、大流量活动参与者判重等海量元素或高度并发场景(对误判有一定容忍)这种方式也许就不再可接受。

Bloom Filter算法

算法描述

误报及误报率

最优的哈希函数个数

位数组个数

特性

应用实例

扩展及应用

参考

本文采用CC BY-SA许可发布,您可以自由的转载分享。

转载请保留出处 BeanMr.
http://blog.beanmr.com/2015/01/08/CheckExisting-BloomFilter/


 Toc