共计 1983 个字符,预计需要花费 5 分钟才能阅读完成。
导读 | 在对响应时间要求比较严格的情况下,如果我们有里面,那么随着集合中元素数量的增加,我们需要的存储空间越来越大,检索时间也越来越长,导致内存过多开销和时间效率变低。 |
如果要判断一个元素是否在集合中,一般的思路是保存集合中的所有元素,然后通过比较来确定。链表、树、哈希表(也叫哈希表、哈希表)等数据结构都是这种方式,存储位置要么是磁盘,要么是内存。很多时候,要么时间换空间,要么空间换时间。
在对响应时间要求比较严格的情况下,如果我们有里面,那么随着集合中元素数量的增加,我们需要的存储空间越来越大,检索时间也越来越长,导致内存过多开销和时间效率变低。
这时候需要考虑的问题是,在数据量比较大的情况下,既能满足时间要求,又能满足空间要求,所以我们需要一种时间和空间消耗都比较小的数据结构和算法。布隆过滤器是一种解决方案。
Bloom Filter, 布隆过滤器由 Bloom 于 1970 年提出。它实际上是一个长二进制向量和一系列随机映射函数, 布隆过滤器可用于检索元素是否在集合中。其优点是空间效率和查询时间远超一般算法,缺点是存在一定的误识别率和删除难度。根据它的特性,应用场景有如下:
布隆过滤器的原理是当一个元素加入到集合中时,通过 K 个哈希函数将该元素映射到一个位数组中的 K 个点,并将它们置为 1。检索时,我们只需要看这些点是否都为 1,就可以(大概)知道它是否存在于集合中。如果这些点中的任何一个有 0,则检查的元素一定不存在。如果它们都是 1,则被选中的元素很可能在那里。
Bloom Filter 与单一哈希函数 Bit-Map 的区别在于,Bloom Filter 使用 k 个哈希函数,每个字符串对应 k 个 bits,从而降低碰撞概率。
由于 Bloom filter 只存储 0 和 1 而不存储具体值,所以在一些机密场合具有先天优势。位图的每一位都是一个位,所以通过位图有 10 亿个位置,位图的大小为 0.12G,插入和查询的时间复杂度为 O(k),k 是哈希函数的个数。
布隆过滤器之所以能够在时间和空间上取得比较高的效率,是因为它牺牲了判断的准确性和删除的便利性。
1. 判断错误
有可能要找的元素不在容器中,但是散列后得到的 k 个位置都是 1。如果布隆过滤器中存储了黑名单,则可以通过创建白名单来存储可能被误判的元素。
对于这个问题,可以通过增加位图数组的大小(位图数组越大,占用的内存越大)和减少哈希冲突来解决。但缺点是会增加占用的内存空间。
另一种解决方案是增加散列函数的数量并减少散列冲突。如果同一个键值等于一个函数,经过两个或多个哈希函数得到相等结果的概率自然会降低。然而,这会导致计算效率的降低,因为时间复杂度退化为 O(hash times)。
2. 难以去除
放置在容器中的元素映射到位数组的 k 个位置中的 1。删除的时候不能简单的直接设置为 0,这样可能会影响其他元素的判断。你可以使用Counting Bloom Filter来解决这个问题。
google 的 guava 就提供了这样的 API.
编写测试代码
import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class GuavaBloomFilter {public static void main(String[] args) {
int total = 1000000;
// default false positive ratefpp0.03
// fpp:There will always be a false positive rate in a Bloom filter
// Because hash collisions are impossible to avoid 100%.
// Bloom filter calls this misjudgment rate false positive probability,abbreviated as fpp
BloomFilter bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);
// Initialize the total bar data into the filter
for (int i = 0; i bfWithFpp = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total, 0.0001);
for (int i = 0; i
![post-qrcode](https://www.xgss.net/wp-content/uploads/2023/07/二维码-微信公众号256x256.jpg)