数据结构

布隆过滤器的数据结构是一个位向量，也就是一个由0、1所组成的向量（下面是一个初始向量）：

[](https://p6-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/60037369c48345058599554ccf87dcb0~tplv-k3u1fbpfcp-zoom-in-crop-mark:1512:0:0:0.awebp?)

添加

每个元素添加进布隆过滤器前，都会经过多个不同的哈希函数，计算出不同的哈希值，然后映射到位向量上，也就是对应的位上面置1：

[](https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/20f90b0f80ad48e2ad07801f9d5a5647~tplv-k3u1fbpfcp-zoom-in-crop-mark:1512:0:0:0.awebp?)

判断存在

判断元素是否存在也是如上图流程，根据哈希函数映射的位置，判断所有映射位置是否都为1，如果是则元素可能存在，否则元素一定不存在。

由于不同的值通过哈希函数之后可能会映射到相同的位置，因此如果一个不存在的元素对应的位位置都被其他元素所设置位1，则查询时就会误判：

[](https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/f8a78ba468ef4eb89060ba18c45af6da~tplv-k3u1fbpfcp-zoom-in-crop-mark:1512:0:0:0.awebp?)

假设上图元素3334并没有加入集合，但是由于它映射的位置已经被其他元素所映射，则查询时会误判。

布隆过滤器：一种低空间成本的判断元素是否存在的方式 - 掘金