转自《程序员代码面试指南 IT名企算法与数据结构题目最优解 ,左程云著》

如果碰到网页黑名单系统、爬虫的网址判重等，如果系统容忍一定程度的失误率，但对空间要求比较严格，往往是要求了解布隆过滤器。

一个布隆过滤器精确代表一个集合，并可以精确判断一个元素是否在集合中。但是有多精确，取决于具体的设计，但不可能完全正确。

哈希函数

输入是任意，输出是固定范围，假设为S，并具有如下性质：

1、典型的哈希函数都有无限的输入值域。

2、传入相同的输入值，返回值一样。

3、传入不同输入值，返回值可能一样，也可能不一样。

4、最重要的性质：很多不同输入值得到的返回值会均匀分布在S上。

第4点是评价一个哈希函数优劣的关键，这种均匀分布与输入值出现的规律无关。比如MD5和SHA1算法。

布隆过滤器

原理

假设有一个长度为m的bit类型的数组，即数组中每个位置只占一个bit，每个bit只有0和1两种状态

bit array.png

再假设一共有k个哈希函数，这些函数的输出域S都大于或等于m，且这些哈希函数彼此独立。那么对同一个输入对象，经过k个哈希函数算出来的结果也是独立的。对算出来的每个结果都对m取余，然后再bit array上把相应位置设置1。

bit array mod.png

把bit类型的数组记为bitMap。处理完所有输入对象后，可能bitMap中已经有很多位置被涂黑。至此，一个布隆过滤器生成完毕，这个代表之前所有输入对象组成的集合。

在检查阶段，如何检查某一个对象是否是之前的某一个输入对象？

一个输入对象，通过k个哈希算出k个值，把k个值对m取余，在bitMap上看这些位置是不是都是黑，如果有一个不为黑，则一定不在集合。如果都是黑，说明在集合，但是这里存在误判。

实现

如果bitMap的大小m相比于输入对象的个数n过小，失误率会变大。

假设黑名单中样本个数为100亿个，记为n；失误率不希望超过0.01%，记为p；每个样本（url）大小64B，当然这个大小不会影响布隆过滤器的大小。

所以n=100亿，p=0.01%，布隆过滤器的大小m由以下公式确定：

根据公式计算出m=19.19n，大约20n，即需要2000亿个bit，也即是25G。

哈希函数的个数由以下公式决定：

计算出约为14个。

然后用25GB的bitMap再单独实现14个哈希函数，根据如上描述生成布隆过滤器。

失误率的计算

失误率就是某个不认识的url，经过k个哈希函数后，在布隆过滤器取余后发现这些位置上都是黑，这样的情况称为一个失误。那么失误率就是看k个位置都是黑的概率。

假设k个哈希函数独立，对于某一个bit位，一个输入对象在被k个哈希函数散列后，这个位置依然没有被涂黑的概率为：

经过n个输入对象后，这个位置依然没有被涂黑的概率为：

被涂黑的概率就是

则在检查阶段，检查k个位置都为黑的概率为：

在时， 。这里m是很大的数，所以，则简化为

误报的解决

通过建立白名单防止误报。比如已经发现某个样本不在布隆过滤器，但每次计算后结果都显示其在布隆过滤器中，则可以把该样本加入白名单中，以后就知道的确不在过滤器中。

代码

爬虫项目中用到了布隆过滤器

[SimpleBloomFilter.java](../../../../gitlab/data-platform/page-feature/rtbreq-frontier/src/main/java/com/buzzinate/util/SimpleBloomFilter.java)

package com.buzzinate.util;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.BitSet;

import org.apache.commons.lang.StringUtils;
import org.apache.log4j.Logger;

public class SimpleBloomFilter{
    private static Logger logger = Logger.getLogger(SimpleBloomFilter.class);
    private static SimpleBloomFilter instance = null;
    private static final int DEFAULT_SIZE = Integer.MAX_VALUE;
    private static final int[] seeds = new int[] { 5, 7, 11, 13, 31, 37, 61 };
    private BitSet bits = new BitSet(DEFAULT_SIZE);
    private SimpleHash[] func = new SimpleHash[seeds.length];

    public static String filename = "/opt/tomcat/bloomfilter";
    private SimpleBloomFilter() {
        for (int i = 0; i < seeds.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
        }
    }

    
    public BitSet getBits() {
        return bits;
    }


    public void setBits(BitSet bits) {
        this.bits = bits;
    }


    public void add(String value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }

    public boolean contains(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    public void saveBit() {
        try {
            
            int count = 0;
            for(int i = 0;i < DEFAULT_SIZE;i ++){
                if(bits.get(i)){
                    count ++ ;
                }
            }
            logger.info("bloomfilter true bits:"+count);
            
            File file = new File(filename+".tmp");
            logger.info("save bloomfilter, path "+ file.getAbsolutePath());
            ObjectOutputStream oos = new ObjectOutputStream(
                    new FileOutputStream(file, false));
            oos.writeObject(bits);
            
            oos.flush();
            oos.close();
            file.renameTo(new File(filename));
            logger.info("saved bloomfilter to " + file.getAbsolutePath());
        } catch (Exception e) {
            logger.error(e, e);
        }
    }

    public BitSet readBit(String path) {
        BitSet bits = new BitSet(DEFAULT_SIZE);
        File file = new File(filename);
        if(StringUtils.isNotBlank(path)){
            file = new File(path);
        }
        logger.info("read bloomfilter, path "+ file.getAbsolutePath());
        if (!file.exists()) {
            logger.info(file.getAbsolutePath()+" not exists!");
            return bits;
        }
        try {
            ObjectInputStream ois = new ObjectInputStream(new FileInputStream(
                    file));
            bits = (BitSet) ois.readObject();
            ois.close();
            int count = 0;
            for(int i = 0;i < DEFAULT_SIZE;i ++){
                if(bits.get(i)){
                    count ++ ;
                }
            }
            logger.info("bloomfilter true bits:"+count);
        } catch (Exception e) {
            logger.error("read bloomfilter fail!", e);
        }
        return bits;
    }

    // 内部类，simpleHash
    public static class SimpleHash {
        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        public int hash(String value) {
            int result = 0;
            int len = value.length();
            for (int i = 0; i < len; i++) {
                result = seed * result + value.charAt(i);
            }
            return (cap - 1) & result;
        }
    }
    
    public static SimpleBloomFilter getInstance(){
        if(instance == null){
            instance = new SimpleBloomFilter();
            if(new File(filename).exists()){
                instance.setBits(instance.readBit(""));
            }
        }
        return instance;
    }
    
    /**
     * 改变实例
     * @param path
     */
    public static boolean changeInstance(String path){
        SimpleBloomFilter tmpInstance = new SimpleBloomFilter();
        File file = new File(path);
        if(System.currentTimeMillis() - file.lastModified() < 3600 * 1000){
            tmpInstance.setBits(tmpInstance.readBit(path));
            instance = tmpInstance;
            return true;
        }
        return false;
    }
    
    /**
     * 返回bit为1的数量
     * @return
     */
    public static int trueBits(){
        int count = 0;
        for(int i = 0;i < DEFAULT_SIZE;i ++){
            if(instance.bits.get(i)){
                count ++ ;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        SimpleBloomFilter filter = new SimpleBloomFilter();
        for (int i = 0; i <100000; i++) {
            filter.add(i + "");
        }

        long t1 = System.currentTimeMillis();
        filter.saveBit();
        long t2 = System.currentTimeMillis();
        System.out.println("it takes " + (t2 - t1)+"ms");
        
        
//      System.out.println("add end");
//      int cnt = 0;
//      for (int i = 200000; i > 100000; i--) {
//          if (filter.contains(i + "")) {
//              cnt++;
//          }
//      }
//
//      System.out.println("total:" + cnt / 300000000.0);
    }

}