关于后端:布隆过滤器

本文已收录至 Github，举荐浏览 👉 Java 随想录
微信公众号：Java 随想录

在开发过程中，常常要判断一个元素是否在一个汇合中。假如你当初要给我的项目增加 IP 黑名单性能，此时你手上有大概 1 亿个歹意 IP 的数据集，有一个 IP 发动申请，你如何判断这个 IP 在不在你的黑名单中？

相似这种问题用 Java 本人的 Collection 和 Map 很难解决，因为它们存储元素自身，会造成内存不足，而咱们只关怀元素存不存在，对于元素的值咱们并不关怀，具体值是什么并不重要。

布隆过滤器能够用来判断某个元素是否在汇合内，具备运行疾速，内存占用小的特点，它是一个保留了很长的二级制向量，同时联合 Hash 函数实现的。而高效插入和查问的代价就是，它是一个基于概率的数据结构，只能通知咱们一个元素相对不在汇合内，对于存在汇合内有肯定的误判率。

因为布隆过滤器中总是会存在误判率，因为哈希碰撞是不可能百分百防止的。布隆过滤器对这种误判率称之为假阳性概率，即：False Positive Probability，简称为 fpp。

在实践中应用布隆过滤器时能够本人定义一个 fpp，而后就能够依据布隆过滤器的实践计算出须要多少个哈希函数和多大的位数组空间。须要留神的是这个 fpp 不能定义为 100%，因为无奈百分保障不产生哈希碰撞。

下图示意向布隆过滤器中增加元素 https://blog.csdn.net/bookssea 和 https://www.abc.com 的过程，它应用了 func1 和 func2 两个简略的哈希函数。

<font color=OrangeRed> 对写入的数据做 H 次 hash 运算定位到数组中的地位，同时将数据改为 1。当有数据查问时也是同样的形式定位到数组中。一旦其中的有一位为 0 则认为数据必定不存在于汇合，否则数据可能存在于汇合中。</font>

通过其原理能够晓得，可咱们能够进步数组长度以及 hash 计算次数来升高误报率，然而相应的 CPU、内存的耗费也会相应的进步；这须要咱们依据本人的业务须要去衡量抉择。

布隆过滤有以下 2 个特点：

只有返回数据不存在，则必定不存在。
返回数据存在，但只能是大概率存在。

在无限的数组长度中寄存大量的数据，即使是再完满的 Hash 算法也会有抵触，所以有可能两个齐全不同的 A、B 两个数据最初定位到的地位是截然不同的。这时拿 B 进行查问时那天然就是误报了。

布隆过滤器判断一个元素存在就是判断对应地位是否为 1 来确定的，然而如果要删除掉一个元素是不能间接把 1 改成 0 的，因为这个地位可能存在其余元素，所以如果要反对删除，最简略的做法就是加一个计数器，就是说位数组的每个位如果不存在就是 0，存在几个元素就存具体的数字，而不仅仅只是存 1，那么这就有一个问题，原本存 1 就是一位就能够满足了，然而如果要存具体的数字比如说 2，那就须要 2 位了，所以带有计数器的布隆过滤器会占用更大的空间。

<dependency>
    <groupId>com.baqend</groupId>
    <artifactId>bloom-filter</artifactId>
    <version>1.0.7</version>
</dependency>

新建一个带有计数器的布隆过滤器 CountingBloomFilter：

import orestes.bloomfilter.FilterBuilder;

public class CountingBloomFilter {public static void main(String[] args) {
        orestes.bloomfilter.CountingBloomFilter<String> cbf = new FilterBuilder(10000,
                0.01).countingBits(8).buildCountingBloomFilter();

        cbf.add("zhangsan");
        cbf.add("lisi");
        cbf.add("wangwu");
        System.out.println("是否存在王五：" + cbf.contains("wangwu")); //true
        cbf.remove("wangwu");
        System.out.println("是否存在王五：" + cbf.contains("wangwu")); //false
    }
}

构建布隆过滤器后面 2 个参数一个就是冀望的元素数，一个就是 fpp 值，前面的 countingBits 参数就是计数器占用的大小，这里传了一个 8 位，即最多容许 255 次反复，如果不传的话这里默认是 16 位大小，即容许 65535 次反复。

<font color=OrangeRed> 倡议应用 Guava 自带的布隆过滤器，间接传入预期的数据量以及 fpp，它会主动帮咱们计算数组长度和哈希次数 </font>

假如在布隆过滤器外面有 k 个哈希函数，m 个比特位（也就是位数组长度），以及 n 个已插入元素，错误率会近似于 (1-ekn/m)k，所以你只须要先确定可能插入的数据集的容量大小 n，而后再调整 k 和 m 来为你的利用配置过滤器。

对于给定的 m（比特位个数）和 n（汇合元素个数），最优的 k（哈希函数个数）值为: (m/n)ln(2)

对于一个 m（比特位个数）和 k（哈希函数个数）值确定的布隆过滤器，增加和判断操作的工夫复杂度都是 O(k)，这意味着每次你想要插入一个元素或者查问一个元素是否在汇合中，只须要应用 k 个哈希函数对该元素求值，而后将对应的比特位标记或者查看对应的比特位即可。

Guava 有自带的布隆过滤器的实现

public class BloomFilterTest {public static void main(String[] args) {long star = System.currentTimeMillis();
        BloomFilter<Integer> filter = BloomFilter.create(Funnels.integerFunnel(),
                // 预计寄存多少数据
                10000000,
                // 能够承受的误报率
                0.01);

        for (int i = 0; i < 10000000; i++) {filter.put(i);
        }

        Assert.isTrue(filter.mightContain(1),"不存在");
        Assert.isTrue(filter.mightContain(2),"不存在");
        Assert.isTrue(filter.mightContain(3),"不存在");
        Assert.isTrue(filter.mightContain(10000000),"不存在");
        long end = System.currentTimeMillis();
        System.out.println("执行工夫：" + (end - star));

    }
}

BitMap 不会存在误判的状况，位图也是布隆过滤器的实现，然而占用内存空间随汇合内最大元素的增大而增大。而布隆过滤器，因为其可能一个 bit 为多个元素作标识，这就保障了它的空间利用率。这 2 种形式依据业务进行抉择。

以 32 位整型为例，它能够示意数字的个数为 2^32. 能够申请一个位图，让每个整数对应的位图中的一个 bit，这样 2^32 个数须要的位图的大小为 512MB。具体实现的思路为：申请一个 512MB 的位图，并把所有的位都初始化为 0；接着遍历所有的整数，对遍历到的数字，把相应的地位上的 bit 设置为 1. 最初判断待查找的数对应的位图上的值是多少，如果是 0，那么示意这个数字不存在，如果是 1，那么示意这个数字存在。

Java 中有 BitMap 的实现类，BitSet

public class BitMapTest {public static void main(String[] args) {int[] array = {3, 8, 5, 7, 1};
                BitSet bitSet = new BitSet(5);
 
                for (int i = 0; i < array.length; i++) {bitSet.set(array, true);
                }
 
                bitSet.stream().forEach(e -> System.out.println(e));
 
        }
}

本篇文章就到这里，感激浏览，如果本篇博客有任何谬误和倡议，欢送给我留言斧正。文章继续更新，能够关注公众号第一工夫浏览。

关于后端:布隆过滤器

问题形容

BloomFilter(布隆过滤器)

fpp

布隆过滤器的特点

布隆过滤器中的数据可不可以删除

布隆过滤器应该设计为多大？

布隆过滤器应该应用多少个哈希函数？

布隆过滤器的工夫复杂度和空间复杂度?

Guava 的布隆过滤器的实现

BitMap