Java集合框架分析（十）——布隆过滤器的简单java实现_JAVA_编程开发_程序员俱乐部

? ? 上一篇已经分析的很透彻了，代码应该很好实现了，来个简单版的，直接定义k=8，忽略P(error)，直接上代码：

class="java">/**
 * 简单的布隆过滤器实现，k值设为8，不计算P(error)值，测试的的时候输入10000个字符串，位集大小设成5000 << 10000
 * @author lenovo
 *
 */
class BloomFilterdemo {
	//设置的位集大小
	private int defaultSize = 5000 << 10000;
	//最大索引位置
	private int basic = defaultSize - 1;
	//建立一个二进制位集
	private BitSet bits = new BitSet(defaultSize);
	private String key;
	/**
	 * 构造函数
	 * @param key 输入的key值
	 */
	public void BloomFilter(String key) {
		this.key = key;

	}
	/**
	 * 随机数生成器
	 * @param key
	 * @return 
	 */
	private int[] lrandom(String key) {
		
		int[] randomsum = new int[8];

		for (int i = 0; i < 8; i++) {
			randomsum[i] = hash(key, i);
		}

		return randomsum;
	}
	/**
	 * 添加元素的方法
	 * @param key
	 */
	public void add(String key) {
		int keycode[] = lrandom(key);
		for (int i = 0; i < 8; i++) {
			bits.set(keycode[i]);
		}

	}
	/**
	 * 判断一个元素是否在表中
	 * @param key
	 * @return
	 */
	public boolean exits(String key) {

		int keyCode[] = lrandom(key);
		if (bits.get(keyCode[0]) && bits.get(keyCode[1])
				&& bits.get(keyCode[2]) && bits.get(keyCode[3])
				&& bits.get(keyCode[4]) && bits.get(keyCode[5])
				&& bits.get(keyCode[6]) && bits.get(keyCode[7])) {
			return true;
		}
		return false;

	}
	/**
	 * 自己定义的hash算法
	 * @param key 输入的key值
	 * @param n 自定义的参数，用来传入不同参数生成不同的随机数
	 * @return
	 */
	public int hash(String key, int n) {

		return (int) (key.hashCode() * 21 / 9 * 4 * 8 * n ^ n);

	}

}

public class BloomFilter {

	public static void main(String[] args) {

		BloomFilterdemo bf = new BloomFilterdemo();
		
		Long aBeginTime = System.currentTimeMillis();// 记录BeginTime
		for (int i = 0; i < 10000; i++) {
			bf.add("" + i);
		}
		Long aEndTime = System.currentTimeMillis();// 记录EndTime
		System.out.println("insert time-->" + (aEndTime - aBeginTime));
		Long lBeginTime = System.currentTimeMillis();// 记录BeginTime
		System.out.println(bf.exits("" + 888888));
		Long lEndTime = System.currentTimeMillis();// 记录EndTime
		System.out.println("seach time--->" + (lEndTime - lBeginTime));

	}
}

?