布隆过滤器是可以用于判断一个元素是不是在一个集合里，并且相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。但是它也是拥有一定的缺点：布隆过滤器是有一定的误识别率以及删除困难的。本文中给出的布隆过滤器的实现，基本满足了日常使用所需要的功能。
| 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了，这个时候我们就可以认为这个字符串是已经存在的了。因此不难发现，这是会存在一定的误判率的，具体由你采用的散列函数质量，以及散列函数的数量确定。
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 |
import java.io.fileinputstream; import java.io.fileoutputstream; import java.io.objectinputstream; import java.io.objectoutputstream; import java.io.serializable; import java.util.bitset; import java.util.concurrent.atomic.atomicinteger;
public class bloomfileter implements serializable { private static final long serialversionuid = -5221305273707291280l; private final int [] seeds; private final int size; private final bitset notebook; private final misjudgmentrate rate; private final atomicinteger usecount = new atomicinteger( 0 ); private final double autoclearrate;
/** * 默认中等程序的误判率：misjudgmentrate.middle 以及不自动清空数据（性能会有少许提升） * * @param datacount * 预期处理的数据规模，如预期用于处理1百万数据的查重，这里则填写1000000 */ public bloomfileter( int datacount) { this (misjudgmentrate.middle, datacount, null ); }
/** * * @param rate * 一个枚举类型的误判率 * @param datacount * 预期处理的数据规模，如预期用于处理1百万数据的查重，这里则填写1000000 * @param autoclearrate * 自动清空过滤器内部信息的使用比率，传null则表示不会自动清理， * 当过滤器使用率达到100%时，则无论传入什么数据，都会认为在数据已经存在了 * 当希望过滤器使用率达到80%时自动清空重新使用，则传入0.8 */ public bloomfileter(misjudgmentrate rate, int datacount, double autoclearrate) { long bitsize = rate.seeds.length * datacount; if (bitsize < 0 || bitsize > integer.max_value) { throw new runtimeexception( "位数太大溢出了，请降低误判率或者降低数据大小" ); } this .rate = rate; seeds = rate.seeds; size = ( int ) bitsize; notebook = new bitset(size); this .autoclearrate = autoclearrate; }
public void add(string data) { checkneedclear();
for ( int i = 0 ; i < seeds.length; i++) { int index = hash(data, seeds[i]); settrue(index); } }
public boolean check(string data) { for ( int i = 0 ; i < seeds.length; i++) { int index = hash(data, seeds[i]); if (!notebook.get(index)) { return false ; } } return true ; }
/** * 如果不存在就进行记录并返回false，如果存在了就返回true * * @param data * @return */ public boolean addifnotexist(string data) { checkneedclear();
int [] indexs = new int [seeds.length]; // 先假定存在 boolean exist = true ; int index;
for ( int i = 0 ; i < seeds.length; i++) { indexs[i] = index = hash(data, seeds[i]);
if (exist) { if (!notebook.get(index)) { // 只要有一个不存在，就可以认为整个字符串都是第一次出现的 exist = false ; // 补充之前的信息 for ( int j = 0 ; j <= i; j++) { settrue(indexs[j]); } } } else { settrue(index); } }
return exist;
}
private void checkneedclear() { if (autoclearrate != null ) { if (getuserate() >= autoclearrate) { synchronized ( this ) { if (getuserate() >= autoclearrate) { notebook.clear(); usecount.set( 0 ); } } } } }
public void settrue( int index) { usecount.incrementandget(); notebook.set(index, true ); }
private int hash(string data, int seeds) { char [] value = data.tochararray(); int hash = 0 ; if (value.length > 0 ) {
for ( int i = 0 ; i < value.length; i++) { hash = i * hash + value[i]; } }
hash = hash * seeds % size; // 防止溢出变成负数 return math.abs(hash); }
public double getuserate() { return ( double ) usecount.intvalue() / ( double ) size; }
public void savefiltertofile(string path) { try (objectoutputstream oos = new objectoutputstream( new fileoutputstream(path))) { oos.writeobject( this ); } catch (exception e) { throw new runtimeexception(e); }
}
public static bloomfileter readfilterfromfile(string path) { try (objectinputstream ois = new objectinputstream( new fileinputstream(path))) { return (bloomfileter) ois.readobject(); } catch (exception e) { throw new runtimeexception(e); } }
/** * 清空过滤器中的记录信息 */ public void clear() { usecount.set( 0 ); notebook.clear(); }
public misjudgmentrate getrate() { return rate; }
/** * 分配的位数越多，误判率越低但是越占内存 * * 4个位误判率大概是0.14689159766308 * * 8个位误判率大概是0.02157714146322 * * 16个位误判率大概是0.00046557303372 * * 32个位误判率大概是0.00000021167340 * * @author lianghaohui * */ public enum misjudgmentrate { // 这里要选取质数，能很好的降低错误率 /** * 每个字符串分配4个位 */ very_small( new int [] { 2 , 3 , 5 , 7 }), /** * 每个字符串分配8个位 */ small( new int [] { 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 }), // /** * 每个字符串分配16个位 */ middle( new int [] { 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 }), // /** * 每个字符串分配32个位 */ high( new int [] { 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 , 109 , 113 , 127 , 131 });
private int [] seeds;
private misjudgmentrate( int [] seeds) { this .seeds = seeds; }
public int [] getseeds() { return seeds; }
public void setseeds( int [] seeds) { this .seeds = seeds; }
}
public static void main(string[] args) { bloomfileter fileter = new bloomfileter( 7 ); system.out.println(fileter.addifnotexist( "1111111111111" )); system.out.println(fileter.addifnotexist( "2222222222222222" )); system.out.println(fileter.addifnotexist( "3333333333333333" )); system.out.println(fileter.addifnotexist( "444444444444444" )); system.out.println(fileter.addifnotexist( "5555555555555" )); system.out.println(fileter.addifnotexist( "6666666666666" )); system.out.println(fileter.addifnotexist( "1111111111111" )); fileter.savefiltertofile( "c:\\users\\john\\desktop\\1111\\11.obj" ); fileter = readfilterfromfile( "c:\\users\\john\\desktop\\111\\11.obj" ); system.out.println(fileter.getuserate()); system.out.println(fileter.addifnotexist( "1111111111111" )); } } |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。
原文链接：https://blog.csdn.net/u014653197/article/details/76397037
查看更多关于JAVA实现较完善的布隆过滤器的示例代码的详细内容...