布隆过滤器

布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于判断一个元素是否在一个集合中。它由一个很长的二进制向量和一组哈希函数组成。当新元素加入集合时，通过哈希函数将其映射到位数组的多个位置并标记为1；查询元素时，同样通过哈希函数映射到位数组的多个位置，如果所有位置都为0，则认为该元素不在集合中，否则可能存在于集合中。由于存在误判率，所以布隆过滤器可能会将不存在的元素误判为存在于集合中。