type
Post
status
Published
date
May 31, 2025 01:37 PM
slug
summary
布隆过滤器实现原理及其优劣。
tags
算法
category
算法拾遗
icon
password
A Bloom filter is a space-efficient probabilistic data structure.
False positive matches are possible, but false negatives are not – in other words, a query returns either "possibly in set" or "definitely not in set". Elements can be added to the set, but not removed (though this can be addressed with the counting Bloom filter variant); the more items added, the larger the probability of false positives.
布隆过滤器主要由 bit 数组(m)和若干哈希函数(k)组成。
当我们向布隆过滤器添加元素时，将其输入若干哈希函数并得到哈希值，检查每个哈希值对应于 bit 数组的值，其若为 0 则置为 1。
当我们向布隆过滤器询问元素时，同样将其输入哈希函数并检查对应 bit 值：
- 若全部 bit 位为 1，则布隆过滤器认为可能存在该元素。 这是因为不同存在元素经由若干哈希函数计算得来的哈希值可能覆盖了不存在元素同样经若干哈希函数计算得来的哈希值。布隆过滤器不允许删除元素也是同样的原因，可能存在不同元素计算得到相同哈希值，待删除元素删除后将对应哈希值位置为 0，可能造成原来存在元素返回不存在。
- 若出现 bit 位为 0，则布隆过滤器认为不可能存在该元素。
相比于其他数据结构，布隆过滤器的优点在于：全量存储但是不存储数据本身，适合有保密需求的场景。空间复杂度 O(m) 和时间复杂度稳定 O(k)，不会随着元素增加而改变。
但是其缺点同样明显：随着元素的增加其误报率会显著上升，并且不允许删除元素。
- 作者:宗海
- 链接:https://nowave.cloud//article/1f7beb96-1d72-8058-abe6-c954a9501804
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
