布隆过滤器

布隆过滤器的原理非常简单，将要过滤的东西通过k个hash函数计算，映射到bitmap数组上（bitmap是逻辑上的，实际实现可以看上一篇文章），将相应的位置设置为1。至于什么误判率之类的，就不细说了，前面都有相关原理的说明。如图：

代码实现

关于BloomFilter的实现，目前我从网络上找到两个版本，都是基于BitSet实现的。第一个版本比较简略，但是能完整的呈现BloomFilter的原理。第二个是比较丰富的，基本上都有。当然，实际工程上，还是推荐使用谷歌的BloomFilter。

版本一：

package com.xushu;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

import sun.security.provider.MD5;

public class BloomFilter {

    
    private static final int BIT_SIZE = 2 << 28; //二进制向量的位数，可以手动算算能存多少
    private static final int[] seeds = new int[]{3, 5, 7, 11, 13, 31, 37, 61};//用于生成信息指纹的8个随机数，最好选取质数
    
    private BitSet bits = new BitSet(BIT_SIZE);
    private Hash[] func = new Hash[seeds.length];//用于存储8个随机哈希值对象
    
    public BloomFilter() {
        for(int i = 0; i < seeds.length; i++){
            func[i] = new Hash(BIT_SIZE, seeds[i]);
        }
    }
    
    /**
     * 像过滤器中添加字符串
     */
    public void addValue(String value){
        //将字符串value哈希为8个或多个整数，然后在这些整数的bit上变为1
        if(value != null){
            for(Hash f : func){
                bits.set(f.hash(value), true);
            }
        }
    }
    
    
    /**
     * 判断字符串是否包含在布隆过滤器中
     */
    public boolean contains(String value){
        if(value == null){
            return false;
        }
        
        boolean ret = true;
        
        //将要比较的字符串重新用上述方法计算hash值，再与布隆过滤器比对
        for(Hash f : func){
            ret = ret && bits.get(f.hash(value));
        }
        
        return ret;
    }
    
    
    /**
     * 随机哈希值对象
     */
    private class Hash{
        private int size; //二进制向量数组大小
        private int seed; //随机数种子
        
        public Hash(int cap, int seed) {
            this.size = 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 (size - 1) & result;
        }
    }
    
    public static void main(String[] args) {
        BloomFilter bf = new BloomFilter();
        List<String> strs = new ArrayList<String>();
        strs.add("123456");
        strs.add("hello word");
        strs.add("transDocId");
        strs.add("123456");
        strs.add("transDocId");
        strs.add("hello word");
        strs.add("test");
        for (int i=0;i<strs.size();i++) {
            String s = strs.get(i);
            boolean bl = bf.contains(s);
            if(bl){
                System.out.println(i+","+s);
            }else{
                bf.addValue(s);
            }
        }
    }
}

版本二：

package com.bjsxt.servlet;

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.BitSet;
import java.util.concurrent.atomic.AtomicInteger;
 
public class BloomFileter implements Serializable {
    private static final long serialVersionUID = -5221305273707291280L;
    private final int[] seeds;
    private final int size;
    private final BitSet notebook;
    private final MisjudgmentRate rate;
    private final AtomicInteger useCount = new AtomicInteger(0);
    private final Double autoClearRate;
 
    /**
     * 默认中等程序的误判率：MisjudgmentRate.MIDDLE 以及不自动清空数据（性能会有少许提升）
     * 
     * @param dataCount
     *            预期处理的数据规模，如预期用于处理1百万数据的查重，这里则填写1000000
     */
    public BloomFileter(int dataCount) {
        this(MisjudgmentRate.MIDDLE, dataCount, null);
    }
 
    /**
     * 
     * @param rate
     *            一个枚举类型的误判率
     * @param dataCount
     *            预期处理的数据规模，如预期用于处理1百万数据的查重，这里则填写1000000
     * @param autoClearRate
     *            自动清空过滤器内部信息的使用比率，传null则表示不会自动清理，
     *            当过滤器使用率达到100%时，则无论传入什么数据，都会认为在数据已经存在了
     *            当希望过滤器使用率达到80%时自动清空重新使用，则传入0.8
     */
    public BloomFileter(MisjudgmentRate rate, int dataCount, Double autoClearRate) {
        long bitSize = rate.seeds.length * dataCount;
        if (bitSize < 0 || bitSize > Integer.MAX_VALUE) {
            throw new RuntimeException("位数太大溢出了，请降低误判率或者降低数据大小");
        }
        this.rate = rate;
        seeds = rate.seeds;
        size = (int) bitSize;
        notebook = new BitSet(size);
        this.autoClearRate = autoClearRate;
    }
 
    public void add(String data) {
        checkNeedClear();
 
        for (int i = 0; i < seeds.length; i++) {
            int index = hash(data, seeds[i]);
            setTrue(index);
        }
    }
 
    public boolean check(String data) {
        for (int i = 0; i < seeds.length; i++) {
            int index = hash(data, seeds[i]);
            if (!notebook.get(index)) {
                return false;
            }
        }
        return true;
    }
 
    /**
     * 如果不存在就进行记录并返回false，如果存在了就返回true
     * 
     * @param data
     * @return
     */
    public boolean addIfNotExist(String data) {
        checkNeedClear();
 
        int[] indexs = new int[seeds.length];
        // 先假定存在
        boolean exist = true;
        int index;
 
        for (int i = 0; i < seeds.length; i++) {
            indexs[i] = index = hash(data, seeds[i]);
 
            if (exist) {
                if (!notebook.get(index)) {
                    // 只要有一个不存在，就可以认为整个字符串都是第一次出现的
                    exist = false;
                    // 补充之前的信息
                    for (int j = 0; j <= i; j++) {
                        setTrue(indexs[j]);
                    }
                }
            } else {
                setTrue(index);
            }
        }
 
        return exist;
 
    }
 
    private void checkNeedClear() {
        if (autoClearRate != null) {
            if (getUseRate() >= autoClearRate) {
                synchronized (this) {
                    if (getUseRate() >= autoClearRate) {
                        notebook.clear();
                        useCount.set(0);
                    }
                }
            }
        }
    }
 
    public void setTrue(int index) {
        useCount.incrementAndGet();
        notebook.set(index, true);
    }
 
    private int hash(String data, int seeds) {
        char[] value = data.toCharArray();
        int hash = 0;
        if (value.length > 0) {
 
            for (int i = 0; i < value.length; i++) {
                hash = i * hash + value[i];
            }
        }
    
        hash = hash * seeds % size;
        // 防止溢出变成负数
        return Math.abs(hash);
    }
 
    public double getUseRate() {
        return (double) useCount.intValue() / (double) size;
    }
 
    public void saveFilterToFile(String path) {
        try (ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(path))) {
            oos.writeObject(this);
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
 
    }
 
    public static BloomFileter readFilterFromFile(String path) {
        try (ObjectInputStream ois = new ObjectInputStream(new FileInputStream(path))) {
            return (BloomFileter) ois.readObject();
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }
 
    /**
     * 清空过滤器中的记录信息
     */
    public void clear() {
        useCount.set(0);
        notebook.clear();
    }
 
    public MisjudgmentRate getRate() {
        return rate;
    }
 
    /**
     * 分配的位数越多，误判率越低但是越占内存
     * 
     * 4个位误判率大概是0.14689159766308
     * 
     * 8个位误判率大概是0.02157714146322
     * 
     * 16个位误判率大概是0.00046557303372
     * 
     * 32个位误判率大概是0.00000021167340
     * 
     * @author lianghaohui
     *
     */
    public enum MisjudgmentRate {
        // 这里要选取质数，能很好的降低错误率
        /**
         * 每个字符串分配4个位
         */
        VERY_SMALL(new int[] { 2, 3, 5, 7 }),
        /**
         * 每个字符串分配8个位
         */
        SMALL(new int[] { 2, 3, 5, 7, 11, 13, 17, 19 }), //
        /**
         * 每个字符串分配16个位
         */
        MIDDLE(new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 }), //
        /**
         * 每个字符串分配32个位
         */
        HIGH(new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
                101, 103, 107, 109, 113, 127, 131 });
 
        private int[] seeds;
 
        private MisjudgmentRate(int[] seeds) {
            this.seeds = seeds;
        }
 
        public int[] getSeeds() {
            return seeds;
        }
 
        public void setSeeds(int[] seeds) {
            this.seeds = seeds;
        }
 
    }
 
    public static void main(String[] args) {
        BloomFileter fileter = new BloomFileter(7);
        System.out.println(fileter.addIfNotExist("1111111111111"));
        System.out.println(fileter.addIfNotExist("2222222222222222"));
        System.out.println(fileter.addIfNotExist("3333333333333333"));
        System.out.println(fileter.addIfNotExist("444444444444444"));
        System.out.println(fileter.addIfNotExist("5555555555555"));
        System.out.println(fileter.addIfNotExist("6666666666666"));
        System.out.println(fileter.addIfNotExist("1111111111111"));
        fileter.saveFilterToFile("C:\\Users\\john\\Desktop\\1111\\11.obj");
        fileter = readFilterFromFile("C:\\Users\\john\\Desktop\\111\\11.obj");
        System.out.println(fileter.getUseRate());
        System.out.println(fileter.addIfNotExist("1111111111111"));
    }
}