布隆过滤器

package cn.march.model.bloom_filter;

/**
 * 
 *
 * 问题描述：
 *
 *      利用位图(bitMap)对数组进行排序：
 *      位图：
 *          简单来讲就是数组存放数据，若存在这个数据则将值置为1或者true
 *          比如现在有数组int[]{4,3,2,6} 利用位图来进行存储的话：
 *          arrays[2] = 1, arrays[3] = 1, arrays[4] = 1, arrays[6] = 1
 *          这样可以通过数组index表示值，1代表其值存在
 *
 *
 */
public class BitMap_Sort {
	
	
	//测试方法
	public static void main(String[] args) {

    		int[] arrays = new int[]{4,3,2,9,8,10,12};

    		bitmap_sort(arrays);

    		for(int array : arrays)
        		System.out.print(array + " ");

		}

	/**
	 * 基本思路：
	 *
	 *      首先计算数组的最值：max和min
	 *      通过max-min+1计算得到位图数组的实际容量new int[max-min+1]
	 *      通过arrays的值对bit_arrays进行初始化;
	 *      考虑到arrays的值存在负数，比如：{1,4,-3,2}
	 *      最小值是-3,所以在对bit_arrays计算的时候：
	 *             for(int array : arrays)
	 *                  bit_arrays[array-min]++;
	 *      这样就消除了负数的影响i
	 *      之后就根据位图来排序arrays
	 *
	 * @param arrays
	*/
	public static void bitmap_sort(int[] arrays) {

		int max = arrays[0];
		int min = max;
		
		//求arrays的最值
		for(int array : arrays) {

			if(max < array)
				max = array;
			if(min > array)
				min = array;

		}

		//对bit_arrays位图数组进行初始化
		int[] bit_arrays = new int[max-min+1];

		for(int array : arrays)
			bit_arrays[array-min]++;

		int index = 0;

		//对arrays进行排序;
		for(int i = 0; i < bit_arrays.length; i++) {

			while(bit_arrays[i] > 0) {

				arrays[index] = i + min;
				index++;
				bit_arrays[i]--;

			}

		}

	}

}

package cn.march.model.bloom_filter;

	
import java.util.*;

public class BloomFilter {

    //布隆过滤器的比特长度
    private static final int DEFAULT_SIZE = 2<<24; 
	

    //选取质数，能很好的降低错误率
    private static final int[] seeds = {3,5,7,11,13,31,37,61};

    private static BitSet bits = new BitSet(DEFAULT_SIZE);
	
    //初始化一个哈希类数组
    private static SimpleHash[] func = new SimpleHash[seeds.length];

    /**
     * 向BitSet添加一个字符串
     * @param value
     */
    private static void addValue(String value) {

        for(SimpleHash fun : func) {

            bits.set(fun.hash(value), true);

        }

    }

    
    public static void add(String value) {
        
        if(value != null)
		if(contains(value))
			throw new RuntimeException("添加的数据已存在!");
		else
			addValue(value);
    }

    //判断一个字符串是否在BitSet中是否存在
    public static 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 static void main(String [] args) {
        
        String value = "dymdmy2120@gmail.com";

        for(int i = 0; i < seeds.length; i++) {

            func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);

        }

        add(value);

        System.out.println(contains(value));

    }



    /**
     * 哈希类：
     * 	 	一个cap容量(2 << 24),即BitSet容量(很大)和选定的一个质数
     * 		通过对应的String value字符串来计算一个对应的hash值
     * 
     * @author antsmarth
     *
     */
    static class SimpleHash {
      
    	//容量(DEFAULT_SIZE)
        private int cap;
        //质数
        private int seed;

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

        }

        //计算hash值
        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;

        }


    }


}