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

Bloom Filter算法

算法描述

误报及误报率

最优的哈希函数个数

位数组个数

特性

应用实例

扩展及应用

参考