「算法?」Bloom Filter碰撞检测算法

Bloom Filter，这是一种常见的碰撞检测算法。

Bloom Filter 作为一种空间效率非常高的概率型数据结构，主要用于判断一个元素是否处于一个集合中。已知的可用于实现Bloom Filter算法的最佳实现是基于二进制向量和哈希函数。

Bloom Filter的实现代码如下：

import java.util.BitSet;
import java.util.Random;
public class BloomFilter {
	private BitSet bitSet;
	private int size;
	private static final int DEFAULT_SIZE = 2 << 24;
	private static final int[] seeds = new int[]{3, 5, 7, 11, 13, 23};
	private Random random;
	public BloomFilter() {
		this(DEFAULT_SIZE);
	}
	public BloomFilter(int size) {
		this.size = size;
		bitSet = new BitSet(size);
		random = new Random();
	}
	public void add(String value) {
		for (int seed : seeds) {
		int pos = hash(value, seed);
		bitSet.set(pos, true);
		}
	}
	public boolean contains(String value) {
		if (value == null) {
			return false;
		}
		boolean ret = true;
		for (int seed : seeds) {
			int pos = hash(value, seed);
			if (!bitSet.get(pos)) {
				ret = false;
				break;
			}
		}
		return ret;
	}
	private int hash(String value, int seed) {
		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 filter = new BloomFilter();
		String[] urls = new String[]{
			"http://www.google.com",
			"http://www.youtube.com",
			"http://www.facebook.com",
			"http://www.google.cn",
			"http://www.sina.com.cn",
			"http://www.baidu.com",
			"http://www.yahoo.com",
			"http://www.sohu.com",
			"http://www.sohu.com",
			"http://www.163.com",
			"http://www.tudou.com",
			"http://www.youku.com"
		};
		for (String url : urls) {
			filter.add(url);
		}
		String[] tests = new String[]{
			"http://www.google.com",
			"http://www.google.cn",
			"http://www.sina.com.cn",
			"http://www.tudou.com",
			"http://www.renren.com",
			"http://www.tmall.com",
		};
		for (String test : tests) {
			System.out.println(filter.contains(test));
		}
	}
}

Bloom Filter的优点在于空间效率非常高，可以判断一个元素是否在集合中，具有很高的率错特性，即存在一定数量的误判。Bloom Filter 适合处理海量数据，较为经典的应用场景是页面布隆过滤器和密码凭证过滤器等。

Bloom Filter的缺点是存在一定的误判率，一旦误判，就会将实际不存在的元素误判为存在。当然，一般情况下，它所造成的影响是可接受的程度的。