bloomfilter【布隆过滤器】

从今天开始仔细学习学习大数据量处理相关的算法，这是第一个算法，布隆过滤器

 

适用范围：可以用来实现数据字典，进行数据的判重，或者集合求交集

基本原理及要点：
对于原理来说很简单，位数组+k个独立hash函数。将hash函数对应的值的位数组置1，
查找时如果发现所有hash函数对应位都是1说明存在，很明显这个过程并不保证查找的
结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位
会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter，用一个
counter数组代替位数组，就可以支持删除了。

还有一个比较重要的问题，如何根据输入元素个数n，确定位数组m的大小及hash函数个
数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下，m至少
要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些，因为还要保证bit数
组里至少一半为 0，则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底
的对数)。

代码实现如下（这个算法的关键是hash函数的设计）：

package com.xhb.algorithms;

import java.security.MessageDigest;
import java.util.BitSet;

public class BloomFilter {
	private BitSet bitset = null;
	private BloomHasher bloomHasher = null;

	public BloomFilter(BloomHasher hashers, int bitarrLength) {
		this.bloomHasher = hashers;
		this.bitset = new BitSet(bitarrLength);
	}

	public boolean isExists(String str) {
		boolean result = true;
		for (int i = 0; i < bloomHasher.getHashers().length; i++) {
			result = result && (bitset.get(bloomHasher.getHashers()[i].hash(str)));
		}
		return result;
	}

	public void addElement(String str) {
		if(isExists(str)) return;
		for (int i = 0; i < bloomHasher.getHashers().length; i++) {
			bitset.set(bloomHasher.getHashers()[i].hash(str), true);
		}
	}


	public static void main(String[] args) {
		BloomFilter filter = new BloomFilter(new BloomHasher(2), 2 << 10);
		String strs[] = { "abc", "", "asdf", "dxerer","abc","abc" };
		for (String str : strs) {
			System.out.println(filter.isExists(str));
			filter.addElement(str);
			System.out.println(filter.isExists(str));
		}

	}
}

class BloomHasher {
	private Hasher[] hashers;

	public Hasher[] getHashers() {
		return hashers;
	}

	public BloomHasher(int hashNum) {
		hashers = new Hasher[hashNum];
		for (int i = 0; i < hashNum; i++) {
			hashers[i] = buildHasher(i);
		}
	}
	
	private Hasher buildHasher(final int i){
		return new Hasher() {
			public int hash(String str) {
				try {
					MessageDigest md5 = MessageDigest
							.getInstance("MD5");
					md5.update(str.getBytes());
					byte[] bytes = md5.digest(str.getBytes());
					int result = bytes[i];
					return result < 0 ? -result : result;
				} catch (Exception e) {
					throw new RuntimeException(e);
				}
			}
		};
	}
}
interface Hasher {
	int hash(String str);
}