JAVA实现较完善的布隆过滤器的示例代码
布隆过滤器是可以用于判断一个元素是不是在一个集合里，并且相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。但是它也是拥有一定的缺点：布隆过滤器是有一定的误识别率以及删除困难的。本文中给出的布隆过滤器的实现，基本满足了日常使用所需要的功能。
0
0
0
0
0
0
0
0
0
0
先简单来说一下布隆过滤器。其实现方法就是：利用内存中一个长度为M的位数组B并初始化里面的所有位都为0，如下面的表格所示：
然后我们根据H个不同的散列函数，对传进来的字符串进行散列，并且每次的散列结果都不能大于位数组的长度。布隆过滤器的误判率取决于你使用多少个不同的散列函数，下面给出的代码中，给出了一些参考的误判率（参考代码中的枚举类：MisjudgmentRate）。现在我们先假定有4个不同散列函数，传入一个字符串并进行一次插入操作，这时会进行4次散列，假设到了4个不同的下标，这个时候我们就会去数组中，将这些下标的位置置为1，数组变更为：
0
1
0
1
1
0
0
0
0
1
如果接下来我们再传入同一个字符串时，因为4次的散列结果都是跟上一次一样的，所以会得出跟上面一样的结果，所有应该置1的位都已经置1了，这个时候我们就可以认为这个字符串是已经存在的了。因此不难发现，这是会存在一定的误判率的，具体由你采用的散列函数质量，以及散列函数的数量确定。
代码如下：
importjava.io.FileInputStream;
importjava.io.FileOutputStream;
importjava.io.ObjectInputStream;
importjava.io.ObjectOutputStream;
importjava.io.Serializable;
importjava.util.BitSet;
importjava.util.concurrent.atomic.AtomicInteger;
publicclassBloomFileterimplementsSerializable{
privatestaticfinallongserialVersionUID=-5221305273707291280L;
privatefinalint[]seeds;
privatefinalintsize;
privatefinalBitSetnotebook;
privatefinalMisjudgmentRaterate;
privatefinalAtomicIntegeruseCount=newAtomicInteger(0);
privatefinalDoubleautoClearRate;
/**
*默认中等程序的误判率：MisjudgmentRate.MIDDLE以及不自动清空数据（性能会有少许提升）
*
*@paramdataCount
*预期处理的数据规模，如预期用于处理1百万数据的查重，这里则填写1000000
*/
publicBloomFileter(intdataCount){
this(MisjudgmentRate.MIDDLE,dataCount,null);
}
/**
*
*@paramrate
*一个枚举类型的误判率
*@paramdataCount
*预期处理的数据规模，如预期用于处理1百万数据的查重，这里则填写1000000
*@paramautoClearRate
*自动清空过滤器内部信息的使用比率，传null则表示不会自动清理，
*当过滤器使用率达到100%时，则无论传入什么数据，都会认为在数据已经存在了
*当希望过滤器使用率达到80%时自动清空重新使用，则传入0.8
*/
publicBloomFileter(MisjudgmentRaterate,intdataCount,DoubleautoClearRate){
longbitSize=rate.seeds.length*dataCount;
if(bitSize<0||bitSize>Integer.MAX_VALUE){
thrownewRuntimeException("位数太大溢出了，请降低误判率或者降低数据大小");
}
this.rate=rate;
seeds=rate.seeds;
size=(int)bitSize;
notebook=newBitSet(size);
this.autoClearRate=autoClearRate;
}
publicvoidadd(Stringdata){
checkNeedClear();
for(inti=0;i=autoClearRate){
synchronized(this){
if(getUseRate()>=autoClearRate){
notebook.clear();
useCount.set(0);
}
}
}
}
}
publicvoidsetTrue(intindex){
useCount.incrementAndGet();
notebook.set(index,true);
}
privateinthash(Stringdata,intseeds){
char[]value=data.toCharArray();
inthash=0;
if(value.length>0){
for(inti=0;i
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。