布隆过滤器

package org.jf.alg;

import java.util.BitSet;

/**
 * 
 * 
 * 
 * @author chenjf
 *
 */
public class BloomFilter 
{
	
	private BitSet bit_array ;
	private final int MAX_SIZE ;
	
	public BloomFilter(int size)
	{

		this(size,2000000000);
	}
	
	public BloomFilter(int size,int max)
	{
		bit_array = new BitSet(size);
		if(max % 8 ==0)
			MAX_SIZE = max / 8;
		else 
			MAX_SIZE = max / 8 +1;
	}
	
	
	public boolean filter(String value)
	{
		int hash1 = this.hashCode1(value);
		int hash2 = this.hashCode2(value);
		int hash3 = this.hashCode3(value);
		int hash4 = this.hashCode4(value);
		if(this.bit_array.get(hash1) &&
				this.bit_array.get(hash2) &&
				this.bit_array.get(hash3) &&
				this.bit_array.get(hash4))
		return true;
		
		else
		{
			this.bit_array.set(hash1);
			this.bit_array.set(hash2);
			this.bit_array.set(hash3);
			this.bit_array.set(hash4);
			
			return false;
		}
	}
	
	public boolean contains(String value)
	{
		int hash1 = this.hashCode1(value);
		int hash2 = this.hashCode2(value);
		int hash3 = this.hashCode3(value);
		int hash4 = this.hashCode4(value);
		if(this.bit_array.get(hash1) &&
				this.bit_array.get(hash2) &&
				this.bit_array.get(hash3) &&
				this.bit_array.get(hash4))
		return true;
		
		return false;
	}
	 
	
	private int hash(String value/*,int cap*/,int seed)
	{
		int result = 0;
		int len = value.length();
		for(int i =0 ;i<len;i++)
		{
			result = seed*result + value.charAt(i);
		}
		return /*Math.abs((cap - 1) & result )*/ Math.abs( result % this.MAX_SIZE );
	}
	
	private int hashCode1(String value)
	{
		return hash(value,13);
	}
	
	private int hashCode2(String value)
	{
		return hash(value,17);
	}
	
	private int hashCode3(String value)
	{
		return hash(value,31);
	}
	
	private int hashCode4(String value)
	{
		return hash(value,41);
	}
	
}