布隆过滤器解法基于上述分析,需要一种能够快速判断元素是否在集合中的数据结构。布隆过滤器(Bloom Filter)可以提供这种能力。布隆过滤器是一个空间效率很高的随机数据结构,对一个元素集合建立索引。...效率高,可实现间隔判断,不需要存储和比较全部元素。当然布隆过滤器也存在误判率问题,需要对参数k和m进行调优,控制在可接受的范围内。...随着大数据的发展,这类空间效率高的随机算法及数据结构还有很多,比如HyperLogLog用于统计基数,Reservoir Sampling用于抽样等。...判断不存在的元素时,可能会产生少量的误判布隆过滤器的原理是,使用多个随机映射函数将元素映射到一个位向量中,判断元素是否在集合中时,检查它在位向量中的位置是否都为1。...添加元素时,将元素分别通过k个函数映射到位向量的k个位置,并将这些位置设为1。判断元素是否存在时,检查它通过k个函数映射的位置是否都是1,如果都是则判断元素存在,否则判断不存在。