布隆过滤器是一种概率型数据结构，用于快速判断一个元素是否在一个集合中。它允许一定的误判率，但不会出现误判为不存在的情况。布隆过滤器的核心思想是通过多个哈希函数将元素映射到一个位数组中，从而实现高效的存储和查询。

布隆过滤器的结构

位数组（Bit Array）：

一个固定大小的位数组，初始时所有位都设置为 0。位数组的大小（m）决定了布隆过滤器的存储空间。

哈希函数（Hash Functions）：

一组独立的哈希函数（k 个），每个哈希函数将输入元素映射到位数组的一个位置。哈希函数的选择和数量会影响布隆过滤器的误判率

工作原理

假设我们有一个布隆过滤器，位数组大小为 m，哈希函数数量为 k。

插入操作

对于每个要插入的元素 x，使用 k 个哈希函数分别计算 k 个位置。

将这些位置对应的位设置为 1。

查询操作

对于每个要查询的元素 y，使用 k 个哈希函数分别计算 k 个位置。检查这些位置对应的位是否都为 1。如果任何一个位置的位为 0，则 y 肯定不在集合中。如果所有位置的位都为 1，则 y 可能在集合中（存在误判）。

错误率计算