布隆过滤器示例

布隆过滤器是一种基于位向量的概率型数据结构，能快速且节省内存地判断元素是否在集合中，但存在假阳性。

添加元素时将其通过k个独立且分布均匀的哈希函数映射到位向量中并将对应位置置1；查询时同样哈希并检查所有位是否为1。

假阳性率可用公式(1−e^(−kn/m))^k近似计算，可通过调整位数m和哈希函数数量k来控制误差率。

最优哈希函数数量k≈(m/n)ln2，通过估算元素数量n后选择合适的m和k来配置过滤器。

插入和查询的时间复杂度均为O(k)，空间效率取决于可接受的假阳性率及元素范围。

常用的快速非加密哈希函数有Murmur、xxHash、FNV等，选择快速且均匀分布的哈希函数能显著提升性能。

布隆过滤器常用于网络应用、数据库、缓存及生物信息等场景，以减少存储开销并加速大规模数据查询。