Bloom filter

Bloom filter的优点:

 

1. 大小固定，增加更多元素到一个Bloom filter不会增加它的大小，仅增加误报的概率
2. 冲突概率低，为了降低冲突概率，Bloom filter引入多个Hash函数，其误报率可近似为:1-exp(-kn/m)

Java实现:

import java.util.BitSet;

public class BloomFilter {
	/* BitSet初始分配2^24个bit */
	private static final int DEFAULT_SIZE = 1 << 25;
	/* 不同哈希函数的种子，一般应取质数 */
	private static final int[] seeds = new int[] { 5, 7, 11, 13, 31, 37, 61 };
	private BitSet bits = new BitSet(DEFAULT_SIZE);
	/* 哈希函数对象 */
	private SimpleHash[] func = new SimpleHash[seeds.length];

	public BloomFilter() {
		for (int i = 0; i < seeds.length; i++) {
			func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
		}
	}

	// 将字符串标记到bits中
	public void add(String value) {
		for (SimpleHash f : func) {
			bits.set(f.hash(value), true);
		}
	}

	// 判断字符串是否已经被bits标记
	public 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 class SimpleHash {
		private int cap;
		private int seed;

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

		// hash函数，采用简单的加权和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;
		}
	}
}

 

 

 

评论

1 楼 jyltiger813 2012-05-15  

这个实现存在问题
多个seeds对应一个BitSet,会增加hash碰撞冲突的概率,既增加误判为已包含的概率
正确的做法应该是一个seed对应一个BitSet
多个BitSet只要有一个不包含既判断为不包含,降低误判概率

public class CompanyBloom implements Serializable{
	/**
	 * 
	 */
	
		
	private static final long serialVersionUID = 1L;
	/* BitSet初始分配2^24个bit */
	private static final int DEFAULT_SIZE = 1 << 933433;// 933433;
	/* 不同哈希函数的种子，一般应取质数 */
	private static final int[] seeds = new int[] { 5, 7, 11, 13, 31, 37, 61};//,73,103,109, 319, 529, 739, 949,113, 323 ,533 ,743, 953 ,121, 331, 541 ,751 ,961,127, 337 ,547, 757, 967 ,131, 341 ,551 ,761, 971,137, 347 ,557, 767,977};//,137, 347 ,557, 767 ,977 ​​};
	HashMap<Integer,BitSet> bitMap = new HashMap<Integer,BitSet>();
//	private BitSet bits = new BitSet(DEFAULT_SIZE);
	/* 哈希函数对象 */
	private SimpleHash[] func = new SimpleHash[seeds.length];

	public CompanyBloom() {
		for (int i = 0; i < seeds.length; i++) {
			func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
			BitSet bit = new BitSet(DEFAULT_SIZE);
			bitMap.put(seeds[i], bit);
		}
		loadFromDisk();
	}

	// 将字符串标记到bits中
	public void add(String value) {
		for (SimpleHash f : func) {
			bitMap.get(f.getSeed()).set(f.hash(value), true);
		//	bits.set(f.hash(value), true);
		}
	}

	// 判断字符串是否已经被bits标记
	public boolean contains(String value) {
		if (value == null) {
			return false;
		}
		boolean ret = true;
		for (SimpleHash f : func) {
			ret = ret && bitMap.get(f.getSeed()).get(f.hash(value));
		}
		return ret;
	}

	/* 哈希函数类 */
	public static class SimpleHash {
		private int cap;
		private int seed;

		public int getSeed() {
			return seed;
		}

		public void setSeed(int seed) {
			this.seed = seed;
		}

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

		// hash函数，采用简单的加权和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);
			}
			//result = result^result;
			return (cap - 1) & result;
			
		}
	}
	public static void main(String args[])
	{
		CompanyBloom bf = new CompanyBloom();
		//bf.loadFromDB();
	//	bf.add("中国人");
		long t1 = System.currentTimeMillis();
		System.out.println("isContain:"+bf.contains("中国人名"));
		System.out.println("time:"+(System.currentTimeMillis()-t1));
		System.out.println("isContain:"+bf.contains("网易"));
		//System.out.println("isContain:"+bf.contains("中国人名"));
		System.out.println("isContain:"+bf.contains("ok"));
		System.out.println("isContain:"+bf.contains("北京分公司1"));
		System.out.println("isContain:"+bf.contains("中国移动"));
		System.out.println("isContain:"+bf.contains("中国3"));
		System.out.println("isContain:"+bf.contains("新浪1"));
		System.out.println("isContain:"+bf.contains("更新日期"));
		System.out.println("isContain:"+bf.contains("计算机软件"));
	//	bf.flush2Disk();
	}

	/**
	 * 
	 */
	private void loadFromDB() {

		Connection con =getConnection();
		String sql = "  SELECT `name` FROM dic_company_name  ";
		//String sql = " SELECT `name` FROM dic_company_name ";//TODO 测试,仅用较少的一部分数据
		  try {
			Statement stmt = con.createStatement();
			  ResultSet rs = stmt.executeQuery(sql);
			  int i = 0;
			 while( rs.next())
			  {i++;
			 // System.out.println("i"+i);
				String cn_name = rs.getString(1);
				add(cn_name);
					System.out.println("i:"+i);
			  }
		} catch (SQLException e) {
			e.printStackTrace();
		}
		finally{
			try {
				con.close();
			} catch (SQLException e) {
				e.printStackTrace();
			}
		}
		
	}

	/**
	 * 
	 */
	private void loadFromDisk() {
		URL url = CompanyBloom.class.getResource("companyBloom");
		ObjectInputStream oin;
		try {
			oin = new ObjectInputStream(new FileInputStream(url.getFile()));
			bitMap = (HashMap<Integer, BitSet>)oin.readObject();
			oin.close();
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		catch (ClassNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	
		
	}

	/**
	 * 
	 */
	private void flush2Disk() {
		
				
				//试图将对象两次写入文件
				try {
					ObjectOutputStream out = new ObjectOutputStream(
							new FileOutputStream("companyBloom"));
					out.writeObject(bitMap);
					out.flush();
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				
		
	}