bloom filter

布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于判断一个元素是否在一个集合中。它由一个很长的二进制向量和一组Hash函数组成。当需要添加元素时，通过Hash函数将元素映射到二进制向量的某个位置，并将该位置标记为1；查询元素时，同样通过Hash函数映射到二进制向量的某个位置，如果该位置为0，则元素一定不在集合中，如果为1，则元素可能在集合中。由于存在误判率，所以布隆过滤器可以过滤掉一定数量的假阳性结果。它广泛应用于缓存、数据库、搜索引擎等领域。