微信大众号：Java随想录
问题描绘
在开发过程中，经常要判别一个元素是否在一个调集中。假设你现在要给项目增加IP黑名单功用，此刻你手上有大约 1亿个恶意IP的数据集，有一个IP发起请求，你怎么判别这个IP在不在你的黑名单中？
类似这种问题用Java自己的Collection和Map很难处理，由于它们存储元素自身，会形成内存不足，而咱们只关心元素存不存在，关于元素的值咱们并不关心，详细值是什么并不重要。
BloomFilter(布隆过滤器)
布隆过滤器能够用来判别某个元素是否在调集内，具有运转快速，内存占用小的特点，它是一个保存了很长的二级制向量，一起结合 Hash 函数完成的。而高效刺进和查询的代价便是，它是一个基于概率的数据结构，只能告知咱们一个元素必定不在调集内，关于存在调集内有一定的误判率。
fpp
由于布隆过滤器中总是会存在误判率，由于哈希磕碰是不或许百分百避免的。布隆过滤器对这种误判率称之为假阳性概率，即：False Positive Probability，简称为 fpp。
在实践中运用布隆过滤器时能够自己定义一个 fpp，然后就能够依据布隆过滤器的理论核算出需求多少个哈希函数和多大的位数组空间。需求留意的是这个 fpp 不能定义为 100%，由于无法百分确保不发生哈希磕碰。
下图表明向布隆过滤器中增加元素 blog.csdn.net/bookssea 和 www.abc.com 的过程，它运用了 func1 和 func2 两个简略的哈希函数。
对写入的数据做 H 次 hash 运算定位到数组中的方位，一起将数据改为 1 。当有数据查询时也是相同的方法定位到数组中。 一旦其间的有一位为 0 则认为数据必定不存在于调集，不然数据或许存在于调集中。
经过其原理能够知道，可咱们能够进步数组长度以及 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次重复。
主张运用Guava自带的布隆过滤器，直接传入预期的数据量以及fpp，它会主动帮咱们核算数组长度和哈希次数
布隆过滤器应该设计为多大？
假设在布隆过滤器里面有 k 个哈希函数，m 个比特位（也便是位数组长度），以及 n 个已刺进元素，错误率会近似于 (1-ekn/m)k，所以你只需求先确认或许刺进的数据集的容量巨细 n，然后再调整 k 和 m 来为你的应用配置过滤器。
布隆过滤器应该运用多少个哈希函数？
关于给定的 m（比特位个数）和 n（调集元素个数），最优的 k（哈希函数个数）值为: (m/n)ln(2)
布隆过滤器的时刻复杂度和空间复杂度?
关于一个 m（比特位个数）和 k（哈希函数个数）值确认的布隆过滤器，增加和判别操作的时刻复杂度都是 O(k)，这意味着每次你想要刺进一个元素或许查询一个元素是否在调集中，只需求运用 k 个哈希函数对该元素求值，然后将对应的比特位符号或许查看对应的比特位即可。
Guava的布隆过滤器的完成
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
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(i, true);
}
bitSet.stream().forEach(e -> System.out.println(e));
}
}
本篇文章就到这儿，感谢阅览，假如本篇博客有任何错误和主张，欢迎给我留言指正。文章持续更新，能够关注大众号第一时刻阅览。
