正文
一、布隆过滤器
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量（数组）和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
布隆过滤器的原理
布隆过滤器就是由一个二进制的数据和一些hash算法维护，如果xiaojie经过hash算法之后，落在下标为0,3,5的位置，那么对应的二进制数组的位置改为1。那么问题来了，如果我有一个值xiaoli经过hash算法之后也落在了0,3,5的位置，那么此时就会产生hash冲突，这就是为什么布隆过滤器会产生误判的原因。所以如果需要避免这种情况，数组就要尽可能的大，然后避免这种碰撞。布隆过滤器并不会存真实的数据，所以对于保密性数据很友好。
应用场景
对URL的去重，比如在爬虫获取数据时候。
反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱（同理，垃圾短信）
缓存穿透，将所有可能存在的数据缓存放到布隆过滤器中，当恶意访问时，直接避免不必要的IO读取数据库空值的操作。
二、代码
测试类代码
package com.xiaojie.test; import com.google.common.hash.BloomFilter; import com.google.common.hash.Funnels; import java.nio.charset.Charset; import java.util.ArrayList; /** * 布隆过滤器 */ public class BlongTest { private static Integer size = 2<<20; public static void main(String[] args) { BloomFilter<String> integerBloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), size, 0.03); for (int i = 0; i < size; i++) { integerBloomFilter.put(i+""); } ArrayList<Integer> errorList = new ArrayList<>(); for (int j = size; j < size + 10000; j++) { // 使用该pai判断key在布隆过滤器中是否存在 返回true 存在 false 表示不存在 if (integerBloomFilter.mightContain(j+"")) { //误判的数据添加到集合 errorList.add(j); } } System.out.println("误判数据的个数:" + errorList.size()); } }
Redis缓存穿透
//提前将数据存入布隆过滤器 @Override public void preBlongData() { List<User> users = userMapper.selectAll(); for (User user:users){ namesBloomFilter.put(user.getName()); } } //查询之前判断 public User getUserByName(String name) { //判断布隆过滤器是否含有该数据 if(!namesBloomFilter.mightContain(name)){ //如果不存在该数据直接返回，而不进行数据库查询 return null; } JSONObject obj= (JSONObject) redisUtil.get(USERKEY + ":" + name); if (null==obj){ System.out.println("缓存中没有该值,查询数据库"); User resultUser = userMapper.selectByName(name); if (null!= resultUser) { redisUtil.set(USERKEY+":"+resultUser.getName(), JSONObject.toJSON(resultUser),60); return resultUser; } } User user = JSONObject.toJavaObject(obj,User.class); return user; }
