小案例：

    给 100*10000个不重复的的字符串，没排过序的，然后再给10000任意数，如何快速判断是否在 100*10000个数当中?

使用guava封装好的 布隆过滤器实现:

pom.xml

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>22.0</version>
</dependency>

demo

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import org.junit.Test;

import java.util.*;

/**
 * Created by ex-zhongbingguo on 2017/8/2.
 */
public class Demo {

    @Test
    public void bfTest(){
        int sum = 100*1000;         //Bit数组大小选择
        int testSum = 10*1000;
        int right = 0;              //正确个数
        int wrong = 0;              //误算个数
        double fpp = 0.03;          //误算率，默认是0.03
        BloomFilter bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), sum, fpp);

        List list = new ArrayList<>(sum);
        Set set = new HashSet<>(sum);

        for (int i = 0 ; i            String uuid = UUID.randomUUID().toString();
            bf.put(uuid);
            list.add(uuid);
            set.add(uuid);
        }

        for (int i = 0; i < testSum; i++){
            String test = i%100==0 ? list.get(i) : UUID.randomUUID().toString();
            if (bf.mightContain(test)){
                if (set.contains(test)){
                    right++;
                }else{
                    wrong++;
                }
            }
        }
        System.out.println("==================right==================" + right);
        System.out.println("==================wrong==================" + wrong);
    }
}

概念

    BloomFilter算法，是一种大数据排重算法，在一个数据量很大的集合里，能断定一个对象不在集合里；

原理

    当一个元素被加入集合时，通过 K 个 Hash 函数将这个元素映射成一个位阵列（Bit array）中的 K 个点，把它们置为 1。

   检索时 ： 如果这些点有任何一个 0，则被检索元素一定不在；

                        如果都是 1，则被检索元素很可能在。

优势

空间效率和查询时间都远远超过一般的算法，布隆过滤器存储空间和插入 / 查询时间都是常数O(k)

布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势

缺点

存在误算(但不会存在漏算)，随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。

数组长度和hash函数个数难以确定

使用场景

数据库查询，过滤查找的不存在的列，减少磁盘的查找的IO次数

垃圾邮件地址过滤

爬虫URL地址去重

解决缓存穿透的问题