布隆算法 BloomFilter

Rexwong

import java.util.BitSet;/** * <p> * 布隆算法 BloomFilter * <i>http://www.googlechinablog.com/2007/07/bloom-filter.html</i> * </p> * <strong>扩展<tt>hash</tt>算法</strong> * <p> * 基本思想：在内存里面开辟一个区域，所有位置为零，然后 用不同的hash算法对要存入的数据计算hash值，每个hash * 值对内存位数求模，得到的数在内存位置上值1，置位之前需要现 判断是否已经置位，对于插入的值，所有的位置都是1时， 才认为 是重复 * </p> *  * @author Rex.wong */public class BloomFilter {private static int defaultSize = 2 << 24;// 2的24次方。private static int basic = defaultSize - 1;private static BitSet bits;// 内存置位static int check(int h) {return basic & h;}static int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}public BloomFilter() {bits = new BitSet(defaultSize);}public boolean contains(String url) {if (url == null) {return true;}int pos1 = check(hash(url.hashCode() + 2));int pos2 = check(hash(url.hashCode() + 4));int pos3 = check(hash(url.hashCode() + 6));if (bits.get(pos1) && bits.get(pos2) && bits.get(pos3)) {return true;}return false;}public void add(String url) {if (url == null) {return;}int pos1 = check(hash(url.hashCode() + 2));int pos2 = check(hash(url.hashCode() + 4));int pos3 = check(hash(url.hashCode() + 6));bits.set(pos1);bits.set(pos2);bits.set(pos3);}public static void main(String[] args) {String ss = "ssss";BloomFilter bf = new BloomFilter();bf.add(ss);System.out.println(bf.contains(ss));}}