一、前言

布隆过滤器-使用场景:主要是针对不存在的,进行查询短路操作,避免无效的查询，防止内存穿透情况发生，主要案例如下

Google 的分布式数据库 Bigtable 使用了布隆过滤器来查找不存在的行或列，以减少磁盘查找的IO次数。@b@Squid 网页代理缓存服务器在 cache digests 中使用了也布隆过滤器。@b@Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据。@b@SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间。@b@Google Chrome浏览器使用了布隆过滤器加速安全浏览服务。@b@Google Guava - 使用bloom过滤器判断是否存在该行（rows）或（colums），以减少对磁盘的访问，提高数据库的访问性能@b@Apache的HBase - 使用bloom过滤器判断是否存在该行（rows）或（colums），以减少对磁盘的访问，提高数据库的访问性能@b@Apache_Cassandra - 使用bloom过滤器判断是否存在该行（rows）或（colums），以减少对磁盘的访问，提高数据库的访问性能@b@比特币 - 使用布隆过滤判断钱包是否同步OK

二、代码示例 

方法1、guava实现BloomFilter布隆过滤器

 依赖包如下http://xwood.net/xwood-gw/mvn-libs/com/google/guava/guava/18.0/

<dependency>@b@	       <groupId>com.google.guava</groupId>@b@	       <artifactId>guava</artifactId>@b@	       <version>18.0</version>@b@	   </dependency>

package com.xwood.demo.main;@b@@b@import java.nio.charset.Charset;@b@@b@import com.google.common.hash.BloomFilter;@b@import com.google.common.hash.Funnels;@b@@b@public class GuavaBloomFilter {@b@	@b@ @b@	public static void main(String[] args) {@b@		@b@		// 参数1:字符编码集, 参数2:加入的key的数量, 参数3: 预期的误判率@b@	    BloomFilter<String> boomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")),1000000,0.0003);@b@	    for (int i = 0; i < 1000000; i++) {@b@	        // 加入key@b@	        boomFilter.put(i+"abc");@b@	    }@b@	    int count =0;@b@	    for (int i = 0; i < 2000000; i++) {@b@	        // 判断是否存在@b@	        if (boomFilter.mightContain(i+"abc")) {@b@	            count ++;@b@	        }@b@	    }@b@	    System.out.println("count :  "+count);@b@	}@b@	@b@@b@}

控制台结果

count :  1000274

方法2、原子demo示例（无第三方依赖）

package bloom;@b@@b@import java.util.ArrayList;@b@import java.util.BitSet;@b@import java.util.List;@b@ @b@public class BloomFilter {@b@	@b@    private static final int DEFAULT_SIZE = 2 << 24;@b@    private static final int[] seeds = new int[] { 5, 7, 11, 13, 31, 37, 61 };@b@    private BitSet bits = new BitSet(DEFAULT_SIZE);@b@    private SimpleHash[] func = new SimpleHash[seeds.length];@b@ @b@    public BloomFilter() {@b@        for (int i = 0; i < seeds.length; i++) {@b@            func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);@b@        }@b@    }@b@ @b@    public void add(String value) {@b@        for (SimpleHash f : func) {@b@            bits.set(f.hash(value), true);@b@        }@b@    }@b@ @b@    public boolean contains(String value) {@b@        if (value == null) {@b@            return false;@b@        }@b@        boolean ret = true;@b@        for (SimpleHash f : func) {@b@            ret = ret && bits.get(f.hash(value));@b@        }@b@        return ret;@b@    }@b@ @b@    // 内部类，simpleHash@b@    public static class SimpleHash {@b@        private int cap;@b@        private int seed;@b@ @b@        public SimpleHash(int cap, int seed) {@b@            this.cap = cap;@b@            this.seed = seed;@b@        }@b@ @b@        public int hash(String value) {@b@            int result = 0;@b@            int len = value.length();@b@            for (int i = 0; i < len; i++) {@b@                result = seed * result + value.charAt(i);@b@            }@b@            return (cap - 1) & result;@b@        }@b@    }@b@ @b@    public static void main(String[] args) {@b@        BloomFilter bf = new BloomFilter();@b@        List<String> strs = new ArrayList<String>();@b@        strs.add("123456");@b@        strs.add("hello word");@b@        strs.add("transDocId");@b@        strs.add("123456");@b@        strs.add("transDocId");@b@        strs.add("hello word");@b@        strs.add("test");@b@        for (int i=0;i<strs.size();i++) {@b@            String s = strs.get(i);@b@            boolean bl = bf.contains(s);@b@            if(bl){@b@                System.out.println(i+","+s);@b@            }else{@b@                bf.add(s);@b@            }@b@        }@b@    }@b@ @b@}

控制台

3,123456@b@4,transDocId@b@5,hello word

方法3：使用Redisson提供的基于Redis布隆过滤器(github:https://github.com/redisson/redisson) - 依赖包路径http://www.xwood.net/xwood-gw/mvn-libs/org/redisson/redisson/

<dependency>@b@    <groupId>org.redisson</groupId>@b@    <artifactId>redisson</artifactId>@b@    <version>3.13.6</version>@b@ </dependency>

import org.redisson.Redisson;@b@import org.redisson.api.RBloomFilter;@b@import org.redisson.api.RedissonClient;@b@import org.redisson.config.Config;@b@@b@/**@b@ * 使用redisson布隆过滤器@b@ */@b@public class RedissonBloomFilter {@b@@b@    // 预计存储元素的个数@b@    private static final long expectedInsertions = 10000L;@b@    // 误判率@b@    private static final double fpp = 0.03;@b@    @b@    private static final String FILTER_NAME = "BF:name";@b@@b@    public static void main(String[] args) {@b@        // 创建redisson连接@b@        Config config = new Config();@b@        config.useSingleServer().setTimeout(1000000).setAddress("redis://localhost:6379");@b@        RedissonClient redissonClient = Redisson.create(config);@b@@b@        // 创建布隆过滤器并初始化@b@        RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter(FILTER_NAME);@b@        bloomFilter.tryInit(expectedInsertions, fpp);@b@@b@        // 存入元素@b@        bloomFilter.add("张三");@b@        bloomFilter.add("李四");@b@@b@        // 检索元素是否存在@b@        System.out.println(bloomFilter.contains("张三"));@b@        System.out.println(bloomFilter.contains("王五"));@b@@b@        // 关闭连接@b@        redissonClient.shutdown();@b@    }@b@}

控制台运行结果

true@b@false