前言:
最近看了一篇文章<>，第一次知道“布隆过滤器”，查了些资料，觉得有必要整理一下。
- 布隆过滤器是什么？
- 它有什么缺点？
- 布隆过滤器的测试
- 解决缓存击穿的问题
一、布隆过滤器是什么？
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
图解：
它本身是一个很长的二进制向量，既然是二进制的向量，那么显而易见的，存放的不是0，就是1。
现在我们新建一个长度为16的布隆过滤器，默认值都是0，就像下面这样：
现在需要添加一个数据：
我们通过某种计算方式，比如Hash1，计算出了Hash1(数据)=5，我们就把下标为5的格子改成1，就像下面这样：
我们又通过某种计算方式，比如Hash2，计算出了Hash2(数据)=9，我们就把下标为9的格子改成1，就像下面这样
还是通过某种计算方式，比如Hash3，计算出了Hash3(数据)=2，我们就把下标为2的格子改成1，就像下面这样：
这样，刚才添加的数据就占据了布隆过滤器“5”，“9”，“2”三个格子。
可以看出，仅仅从布隆过滤器本身而言，根本没有存放完整的数据，只是运用一系列随机映射函数计算出位置，然后填充二进制向量。
二、它有什么优缺点？
优点：可以高效的查询和插入，它可以告诉你一条数据一定不存在或者可能存在。并且占用非常少的内存空间。
例如：在10亿条数据中判断一条数据的是否存在？
如果用HashSet来处理，他的时间复杂度是O(1),但是他的空间复杂度呢？哈希值是integer类型，一条数据的哈希值占用的空间是4个字节，一共10亿*4/1024/1024/1024约等于3.7G，占用空间太大了。
如果用布隆过滤器呢，因为integer的最大2147483647，所以我们需要定义一个长度为2147483647的bit型数组，如我们所知，每个位置只占一个bit，每个位置只有0和1两种状态, 假如一个数据是哈希是2，我们就可以把数组坐标2的部位标记为1，这个bit数组将是00100.....000;再来一个数据的哈希是5，这个bit数据将是：00100100...000,以此类推。这样就可以存储所有可能的值。8个bit一个字节，占用的空间是2147483647/8/1024/1024=256M
缺点：布隆过滤器期有一定的误差率，数据越多，误差率越大。为了减少误差率，我们可以使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit 位置 1。例如上面图解。
如果要判断一个数据是否存在，我们只需要判断他的不同哈希函数值在 bit 位置中对应的是否为1就可以了，如果有不为1，肯定不存在；如果都为1，可能存在也可能不存在，这是因为哈希值（又叫散列）具有“散列冲突”（两个散列值相同，两个输入值很可能是相同的，也可能不同）的原因。
布隆过滤器删除困难，为什么呢？你想想，你要删除一个数据，把对应bit位置的数据改为0，假如别的数据的哈希值也占用这个位置，不就乱套了。
算法特点：1、因使用哈希判断，时间效率很高。空间效率也是其一大优势。2、有误判的可能，需针对具体场景使用。3、因为无法分辨哈希碰撞，所以不是很好做删除操作。
三、布隆过滤器的测试
测试代码一
public class BloomFilterTest {
private static final int insertions = 1000000; //100w
@Test
public void bfTest(){
//初始化一个存储string数据的布隆过滤器，初始化大小100w,不能设置为0
BloomFilter<string> bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), insertions,0.001);
//初始化一个存储string数据的set，初始化大小100w
Set<string> sets = new HashSet<>(insertions);
//初始化一个存储string数据的set，初始化大小100w
List<string> lists = new ArrayList<string>(insertions);
//向三个容器初始化100万个随机并且唯一的字符串---初始化操作
for (int i = 0; i < insertions; i++) {
String uuid = UUID.randomUUID().toString();
bf.put(uuid);
sets.add(uuid);
lists.add(uuid);
}
int wrong = 0;//布隆过滤器错误判断的次数
int right = 0;//布隆过滤器正确判断的次数
for (int i = 0; i < 10000; i++) {
String test = i%100==0?lists.get(i/100):UUID.randomUUID().toString();//按照一定比例选择bf中肯定存在的字符串
if(bf.mightContain(test)){
if(sets.contains(test)){
right ++;
}else{
wrong ++;
}
}
}
System.out.println("=================right====================="+right);//100
System.out.println("=================wrong====================="+wrong);
}
}
/<string>/<string>/<string>/<string>测试代码二
private static int size = 1000000;//预计要插入多少数据
private static double fpp = 0.01;//期望的误判率
private static BloomFilter<integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);
public static void main(String[] args) {
//插入数据
for (int i = 0; i < 1000000; i++) {
bloomFilter.put(i);
}
int count = 0;
for (int i = 1000000; i < 2000000; i++) {
if (bloomFilter.mightContain(i)) {
count++;
System.out.println(i + "误判了");
}
}
System.out.println("总共的误判数:" + count);
}
/<integer>
不同的数据结构有不同的适用场景和优缺点，你需要仔细权衡自己的需求之后妥善适用它们，布隆过滤器就是践行这句话的代表。
四、缓存击穿的问题
什么是缓存击穿？
正常情况下，我们会把经常用的数据放入缓存中，一个请求进来，先去缓存中查询，如果有数据就返回，如果没有就查询数据库，然后再把数据库中的数据放入缓存中。
但是呢，假如数据也没有数据呢？这样大量的请求就会不断的去查询数据库，造成数据库压力过大甚至崩溃。
为什么不把所有的数据都放入缓存呢？
因为所有数据都放入缓存，会消耗大量的空间，也不符合缓存的初衷，不能暴力的把所有数据都放入缓存。
怎么解决呢？
可以使用布隆过滤器，缓存所有的key相关的信息，上面已经说过了，布隆过滤不仅效率高，而且占用空间小。如果布隆过滤器判断不存在就不用查缓存或者数据库了。
閱讀更多 一個程序員的獨白 的文章
