package bloom;
/**
* 项目名：SpiderCrawler
* 文件名：BloomFilterTest.java
* 作者：zhouyh
* 时间：2014-8-29 下午02:54:56
* 描述：TODO(用一句话描述该文件做什么)
*/
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.BitSet;
import java.util.Scanner;
/**
* 描述： 布隆过滤器，传统的布隆过滤器不支持从集合中删除成员
*/
public class BloomFilterTest {
//DEFAULT_SIZE为2的29次方，即此处的左移28位
private static final int DEFAULT_SIZE = 2<<28;
/*
* 不同哈希函数的种子，一般取质数
* seeds数组共有8个值，则代表采用8种不同的哈希函数
*/
private int[] seeds = new int[]{3, 5, 7, 11, 13, 31, 37, 61};
/*
* 初始化一个给定大小的位集
* BitSet实际是由“二进制位”构成的一个Vector。
* 假如希望高效率地保存大量“开－关”信息，就应使用BitSet.
*/
private BitSet bitSets = new BitSet(DEFAULT_SIZE);
//构建hash函数对象
private SimpleHash[] hashFuns = new SimpleHash[seeds.length];
//布隆过滤器配置文件存放路径
private String path = "";
public BloomFilterTest(String path){
/**
* 给出所有的hash值，共计seeds.length个hash值。共8位。
* 通过调用SimpleHash.hash(),可以得到根据8种hash函数计算得出hash值。
* 传入DEFAULT_SIZE(最终字符串的长度），seeds[i](一个指定的质数)即可得到需要的那个hash值的位置。
*/
for(int i=0; i<seeds.length; i++){
hashFuns[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
}
//配置文件路径地址
this.path = path;
}
/**
* 描述：将给定的字符串标记到bitSets中，即设置字符串的8个函数值的位置为1
*/
public synchronized void add(String value){
for(SimpleHash hashFun : hashFuns){
bitSets.set(hashFun.hash(value), true);
}
}
/**
* 描述：判断给定的字符串是否已经存在在bloofilter中，如果存在返回true，不存在返回false
*/
public synchronized boolean isExit(String value){
//判断传入的值是否为null
if(null == value){
return false;
}
for(SimpleHash hashFun : hashFuns){
if(!bitSets.get(hashFun.hash(value))){
//如果判断8个hash函数值中有一个位置不存在即可判断为不存在Bloofilter中
return false;
}
}
return true;
}
/**
* 描述：读取配置文件
*/
public void init(){
File file = new File(path);
FileInputStream in = null;
try {
in = new FileInputStream(file);
long lt = System.currentTimeMillis();
read(in);
System.out.println(System.currentTimeMillis()-lt);
System.out.println(Runtime.getRuntime().totalMemory());
}catch(Exception e){
e.printStackTrace();
}finally{
try {
if(in!=null){
in.close();
in = null;
}
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
/**
* 描述：根据传入的流，初始化bloomfilter
*/
private void read(InputStream in){
if(null == in){ //如果in为null，则返回
return;
}
int i = 0;
InputStreamReader reader = null;
try {
//创建输入流
reader = new InputStreamReader(in, "UTF-8");
BufferedReader buffReader = new BufferedReader(reader, 512);
String theWord = null;
do {
i++;
theWord = buffReader.readLine();
//如果theWord不为null和空，则加入Bloomfilter中
if(theWord!=null && !theWord.trim().equals("")){
add(theWord.split(" ")[1]);
// System.out.println(theWord.split(" ")[1]);
}
if(i%10000 == 0){
// System.out.println(i);
// System.out.println(theWord.split(" ")[1]);
}
if(i%1000000 == 0){
System.out.println(i);
break;
}
} while (theWord != null);
} catch (IOException e){
e.printStackTrace();
} finally{
//关闭流
try {
if(reader != null){
reader.close();
reader = null;
}
if(in != null){
in.close();
in = null;
}
} catch (IOException e) {
// TODO: handle exception
e.printStackTrace();
}
}
}
/**
* 描述：TODO(这里用一句话描述这个方法的作用)
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BloomFilterTest bloomFilterTest = new BloomFilterTest("D:\学习\实验室项目\ImageNet图片爬取\fall11_urls.txt");
bloomFilterTest.init();
Scanner sc = new Scanner(System.in);
while(true){
System.out.println("输入网址：");
String s = sc.nextLine();
System.out.println(bloomFilterTest.isExit(s));
}
// test();
// System.out.println(Integer.toBinaryString(DEFAULT_SIZE-1));
}
public static void test(){
int tt1 = 2<<28;
int tt2 = 2<<29;
int tt3 = 2<<30;
int tt4 = 2<<1;
System.out.println(Integer.toBinaryString(tt1)+" "+Integer.toBinaryString(tt1).length());
System.out.println(Integer.toBinaryString(tt2)+" "+Integer.toBinaryString(tt2).length());
System.out.println(Integer.toBinaryString(tt3-1)+" "+Integer.toBinaryString(tt3).length());
System.out.println(Integer.toBinaryString(tt4)+" "+Integer.toBinaryString(tt4).length());
BitSet b = new BitSet(tt3);
}
public static class SimpleHash {
/*
* cap为DEFAULT_SIZE，即用于结果的最大字符串的值
* seed为计算hash值的一个key值，具体对应上文中的seeds数组
*/
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 length = value.length();
for(int i=0; i<length; i++){
result = seed*result + value.charAt(i);
}
//011..11共32位，故&运算以后可以取后31位
return (cap-1) & result;
}
}
}
此处应该注意Bitset最多只有32位
根据别人的数据适当选择大小
