package cn.zhf.test;
import java.io.BufferedReader;
import java.io.DataInput;
import java.io.DataOutput;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
public class BloomFilter {
private BitSet bs;
private int bitArraySize = 100000000;
private int numHashFunc = 6;
public BloomFilter(){
bs = new BitSet(bitArraySize);
}
public void add(E obj){
int[] indexes = getHashIndexes(obj);
for(int index : indexes)
bs.set(index);
}
public boolean contains(E obj){
int[] indexes = getHashIndexes(obj);
for(int index : indexes)
if(bs.get(index) == false)
return false;
return true;
}
public void union(BloomFilter other){
bs.or(other.bs);
}
/*粗略实现，采用MD5散列作为java随机数生成器的种子并取k个随机数作为索引*/
public int[] getHashIndexes(E obj){
int[] indexes = new int[numHashFunc];
long seed = 0;
byte[] digest;
try {
MessageDigest md = MessageDigest.getInstance("MD5");
md.update(obj.toString().getBytes());
digest = md.digest();
for(int i=0;i<6;i++)
seed = seed^(((long)(digest[i] & 0xFF)) << (8*i));
} catch (NoSuchAlgorithmException e) {
e.printStackTrace();
}
Random gen = new Random(seed);
for(int i=0;i<numHashFunc;i++)
indexes[i] = gen.nextInt(bitArraySize);
return indexes;
}
public void write(DataOutput out) throws IOException{
int byteArraySize = (int)(bitArraySize / 8);
byte[] byteArray = new byte[byteArraySize];
for(int i=0;i<byteArraySize;i++){
byte nextElement = 0;
for(int j=0;j<8;j++){
if(bs.get(8*i+j))
nextElement |= 1<<j;
}
byteArray[i] = nextElement;
}
out.write(byteArray);
}
public void readFileds(DataInput in) throws IOException{
int byteArraySize = (int)(bitArraySize / 8);
byte[] byteArray = new byte[byteArraySize];
in.readFully(byteArray);
for(int i=0;i
byte nextByte = byteArray[i];
for(int j=0;j
if(((int)nextByte & (1
bs.set(8*i+j);
}
}
}
public Map readFile(String filePath){
BufferedReader br;
Map map = new HashMap();
try {
br = new BufferedReader(new InputStreamReader(
new FileInputStream(filePath)));
int i = 0;
for (String line = br.readLine(); line != null; line = br.readLine()) {
map.put(i++, line);
}
br.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
return map;
}
public static void main(String[] args) {
BloomFilter bf = new BloomFilter();
Map map = bf.readFile("C:\Users\zhf\Desktop\test.txt");
for(Map.Entry m : map.entrySet())
bf.add(m.getValue());
boolean flag = bf.contains("15");
System.out.println(flag);
}
}
