bloomfilter.java

发布/订阅系统路由重配算法,可应用于ad hoc环境

/*
 * project: RebecaSim
 * package: broker
 * file:    BloomFilter.java
 * 
 * version: 0.1
 * date:    10.05.2005
 * 
 * This software is part of the diploma thesis "Ein adaptives Brokernetz 
 * für Publish/Subscribe Systeme".
 */
package broker;

import util.*;

import java.util.*;

/**
 * TODO Insert class description here.
 *
 * @version 10.05.2005
 * @author  parzy
 */
public class BloomFilter {

	/**
	 * Behave as a normal probabilistic Bloom filter.
	 */
	private static final int PROBABILISTIC = 0;
	
	/**
	 * Behave as a correct filter without false positives.
	 */
	private static final int REFERENCE = 1;
	
	/**
	 * The hash seeds.
	 */
	private static long[] hashSeeds = { 7832275170439507118L,
									    2482592291693527392L,
									    1275884113434883813L,
									    6185545544504729010L,
									    8640793470997726979L,
									   -1468240610051773710L,
									    1964100172467432027L,
									    7390923261026300538L,
									   -4070705372186417056L,
									   -1796930593486845647L,
									   -4984397356511947490L };
	
	/**
	 * The available hash functions.
	 */
	private static HashFunction[] hashs = { new HashFunction(hashSeeds[0]),
                                            new HashFunction(hashSeeds[1]),
                                            new HashFunction(hashSeeds[2]),
                                            new HashFunction(hashSeeds[3]),
                                            new HashFunction(hashSeeds[4]),
                                            new HashFunction(hashSeeds[5]),
                                            new HashFunction(hashSeeds[6]),
                                            new HashFunction(hashSeeds[7]),
                                            new HashFunction(hashSeeds[8]),
                                            new HashFunction(hashSeeds[9]) };
	
	/**
	 * Behave as a normal Bloom filter.
	 */
	private static int filterMethod = PROBABILISTIC;
	
	/**
	 * The Bloom filter's bit array.
	 */
	private int[] bits;
	
	/**
	 * Number of used hash functions.
	 */
	private int numberOfHashs;
	
	/**
	 * The Bloom filter's capacity (number of available bits).
	 */
	private int capacity;
	
	/**
	 * The Bloom filter's size (number of stored entries).
	 */
	private int size;
	
	/**
	 * An array to store references to the correct ids.
	 * This allows a measurement of the false positive rate.
	 */
	private ID[] ids;
	
	public static void initialize(Properties properties) {
		// set the filter method
		if(properties.getProperty("filterMethod") != null) {
			if(properties.getProperty("filterMethod").equalsIgnoreCase("PROBABILISTIC")) {
				filterMethod = PROBABILISTIC;
			}
			else if(properties.getProperty("filterMethod").equalsIgnoreCase("REFERENCE")) {
				filterMethod = REFERENCE;
			}
		}
		// set the hash seeds
		for(int i = 0; i<hashSeeds.length; i++){
			if(properties.getProperty("hashSeed"+i) != null) {
				hashSeeds[i] = Long.parseLong(properties.getProperty("hashSeeds"+i));
				hashs[i] = new HashFunction(hashSeeds[i]);
			}
		}
	}
	
	/**
	 * Creates a new bloom filter with a capacity of at least n bits which
	 * uses k hash functions.
	 * @param n the ensured capacity.
	 * @param k the number of used hash functions.
	 */
	public BloomFilter(int n, int k){
		// store the correct id references 
		if(filterMethod == REFERENCE){
			this.numberOfHashs = 0;
			this.ids = new ID[n];
			this.capacity = n;
			this.bits = null;
			this.size = 0;
		}
		// store hashed bits in a bit array
		else if(filterMethod == PROBABILISTIC){
			this.numberOfHashs = k;
			this.bits = new int[n/32 + 1];
			this.ids = null;
			this.capacity = bits.length * 32;
			this.size = 0;
		}
	}
	
	/**
	 * Adds an id to the Bloom filter.
	 * @param value the value to add.
	 */
	public void add(ID id){
		if(filterMethod == REFERENCE){
			// store the correct id
			ids[size%capacity] = id;
			size++;
		}
		else if(filterMethod == PROBABILISTIC){
			// real Bloom filter behaviour
			for(int i = 0, value = id.hashCode(); i < numberOfHashs; i++){
				setBit((hashs[i].hash(value) & 0x0fffffff) % capacity);
			}
			size++;
		}
	}
	
	
	

	/**
	 * Queries the Bloom filter, if it contains the given element. 
	 * @param value the element-
	 * @return true if the Bloom filter probably contains the given element.
	 */
	public boolean contains(ID id){
		if(filterMethod == REFERENCE){
			// when the correct id is stored
			for(int i=0, n=Math.min(size,capacity); i<n; i++){
				if(ids[i]==id){
					return true;
				}
			}
			return false;
		}
		// real Bloom filter behaviour
		else if(filterMethod == PROBABILISTIC){
			for(int i = 0, value = id.hashCode(); i < numberOfHashs; i++){
				if(!containsBit((hashs[i].hash(value) & 0x0fffffff) % capacity)){
					return false;
				}
			}
			return true;
		}
		return false;
	}
	
	/**
	 * Returns the number of added elements.
	 * @return the number of added elements.
	 */
	public int size() {
		return size;
	}
	
	/**
	 * Sets the specified bit.
	 * @param n the bit's number.
	 */
	private void setBit(int n){
		bits[n/32] |= (1 << (n%32)); 
	}
	
	/**
	 * Tests whether the specified bit is set.
	 * @param n the bit's number.
	 * @return true if the bit is set, otherwise false.
	 */
	private boolean containsBit(int n){
		return (bits[n/32] & (1 << (n%32))) != 0;
	}
}