布隆过滤器
Bloom Filter 是由Howard Bloom 在 1970 年提出的二进制向量数据结构,它具有很好的空间和时间效率,被用来检测一个元素是不是集合中的一个成员。如果检测结果为是,该元素不一定在集合中;但如果检测结果为否,该元素一定不在集合中。因此Bloom filter具有100%的召回率。这样每个检测请求返回有“在集合内(可能错误)”和“不在集合内(绝对不在集合内)”两种情况,可见 Bloom filter 是牺牲了正确率和时间以节省空间。
当然布隆过滤器也有缺点,主要是误判的问题,随着数据量的增加,误判率也随着增大,解决办法:可以建立一个列表,保存哪些数值是容易被误算的。
Bloom Filter最大的特点是不会存在false negative,即:如果contains()返回false,则该元素一定不在集合中,但会存在一定的true negative,即:如果contains()返回true,则该元素可能在集合中。
Bloom Filter在很多开源框架都有实现,例如:
Elasticsearch:org.elasticsearch.common.util.BloomFilter
guava:com.google.common.hash.BloomFilter
Hadoop:org.apache.hadoop.util.bloom.BloomFilter(基于BitSet实现)
有兴趣可以看看源码。
BitSet的基本原理
最后再了解一下BitSet的基本原理,BitSet是位操作的对象,值只有0或1,内部实现是一个long数组,初始只有一个long数组,所以BitSet最小的size是64,当存储的数据增加,初始化的Long数组已经无法满足时,BitSet内部会动态扩充,最终内部是由N个long来存储,BitSet的内部扩充和List,Set,Map等得实现差不多,而且都是对于用户透明的。
1G的空间,有 8*1024*1024*1024=8589934592bit,也就是可以表示85亿个不同的数。
BitSet用1位来表示一个数据是否出现过,0为没有出现过,1表示出现过。在long型数组中的一个元素可以存放64个数组,因为Java的long占8个byte=64bit,具体的实现,看看源码:
首先看看set方法的实现:
public void set(int bitIndex) {
if (bitIndex < 0) //set的数不能小于0
throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
int wordIndex = wordIndex(bitIndex);//将bitIndex右移6位,这样可以保证每64个数字在long型数组中可以占一个坑。
expandTo(wordIndex);
words[wordIndex] |= (1L << bitIndex); // Restores invariants
checkInvariants();
}
get命令实现:
public boolean get(int bitIndex) {
if (bitIndex < 0)
throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
checkInvariants();
int wordIndex = wordIndex(bitIndex);//和get一样获取数字在long型数组的那个位置。
return (wordIndex < wordsInUse)
&& ((words[wordIndex] & (1L << bitIndex)) != 0);//在指定long型数组元素中获取值。
}
BitSet容量动态扩展:
private void ensureCapacity(int wordsRequired) {
if (words.length < wordsRequired) {
// Allocate larger of doubled size or required size
int request = Math.max(2 * words.length, wordsRequired);//默认是扩大一杯的容量,如果传入的数字大于两倍的,则以传入的为准。
// wordsRequired = 传入的数值右移6位 + 1
words = Arrays.copyOf(words, request);
sizeIsSticky = false;
}
}
BitSet中实现了Cloneable接口,并定义在表中列出的方法:
SN
Methods with 描述
1 |
void and(BitSet bitSet)
与运算调用的内容BitSet中对象与那些指定bitSet。结果存放到调用对象。 |
2 |
void andNot(BitSet bitSet)
对于bitSet每1位,在调用BitSet中的相应位清零。 |
3 |
int cardinality( )
返回BitSet的容量。 |
4 |
void clear( )
所有位清零。 |
5 |
void clear(int index)
index指定的位清零。 |
6 |
void clear(int startIndex, int endIndex)
将从startIndex到endIndex清零。 |
7 |
Object clone( )
重复调用BitSet中对象。 |
8 |
boolean equals(Object bitSet)
返回true如果调用位设置相当于一个在bitSet通过。否则,该方法返回false。 |
9 |
void flip(int index)
逆转由index指定的位。 |
10 |
void flip(int startIndex, int endIndex)
反转将从startIndex位到endIndex. |
11 |
boolean get(int index)
返回指定索引处的位的当前状态。 |
12 |
BitSet get(int startIndex, int endIndex)
返回一个BitSet中,它包含的比特将从startIndex到endIndex.1。调用对象不被改变。 |
13 |
int hashCode( )
返回调用对象的哈希代码。 |
14 |
boolean intersects(BitSet bitSet)
如果至少有一个对调用对象和bitSet内相应位为1,则返回true。 |
15 |
boolean isEmpty( )
返回true如果在调用对象中的所有位均为零。 |
16 |
int length( )
返回到持有调用BitSet中的内容所需的比特数。这个值是由最后1位的位置决定的。 |
17 |
int nextClearBit(int startIndex)
返回下个清零位的索引,(即,下一个零位),从由startIndex指定的索引开始 |
18 |
int nextSetBit(int startIndex)
返回下一组位(即,下一个1比特)的索引,从由startIndex指定的索引开始。如果没有位被设置,则返回1。 |
19 |
void or(BitSet bitSet)
OR值调用的内容BitSet中对象,通过BitSet指定。结果被放置到调用对象。 |
20 |
void set(int index)
设置由index指定的位。 |
21 |
void set(int index, boolean v)
设置由index指定在v. true为传递的值的位设置位,false则清除该位。 |
22 |
void set(int startIndex, int endIndex)
设置位将从startIndex到endIndex.1。 |
23 |
void set(int startIndex, int endIndex, boolean v)
设置位从startIndex到endIndex.1,在真正传递的值v设置位,清除位为false。 |
24 |
int size( )
返回位在调用BitSet中对象的数量。 |
25 |
String toString( )
返回字符串相当于调用BitSet中的对象。 |
26 |
void xor(BitSet bitSet)
在异或调用BitSet中对象的内容与由BitSet指定。结果存放到调用对象。
|
BloomFilter的使用场景
1,爬虫的URL过滤。
2,日志分析
3,用户数统计等等等
总之使用布隆过滤器应该是可能容忍小概率误判的场景,不然慎用。。。
分享到:
相关推荐
C++实现的布隆过滤器,其中使用到的bitset也是自己简单实现的一个BitContainer。可以处理千万条到亿条记录的存在性判断。做成dll可以在很多场合使用,如自己写爬虫,要判断一个url是否已经访问过,判断一个单词是否...
下面小编就为大家带来一篇布隆过滤器(Bloom Filter)的Java实现方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
redis-bloomFilter是基于redis的bitset实现的bloomfilter.具体原理和实现思路可以参考 使用 redis-bloomFilter发布在JitPack,可以选择下载源码编译,或者通过jitpack源添加依赖。 使用Maven添加依赖 添加jitpack源 ...
盛开 编译安装 $ git clone https://github.com/abenhlal/bloom.git $ cd bitset $ mkdir build $ cd build $ cmake .. $ make $ make test $ sudo make install ... bloom_filter_t *b1 = bloom_new (hash_
This is the bloom filter of 2.5 Million ... BloomFilter bf=new BloomFilter(); BitSet bitSet=bf.readBit(fileName); bf.setBits(bitSet); System.out.println(bf.exist("password")); } it will says true.
布隆过滤器是一种节省空间的概率数据结构,用于确定元素是否属于集合。 布隆过滤器允许错误肯定(可能在集合中),但不允许错误否定(绝对不在集合中)。 如果您不熟悉Bloomfilters,请阅读《 。 bloomfilter软件包...
bitset用法bitset用法bitset用法bitset用法bitset用法bitset用法
C语言头文件 BITSETC语言头文件 BITSETC语言头文件 BITSETC语言头文件 BITSETC语言头文件 BITSETC语言头文件 BITSETC语言头文件 BITSETC语言头文件 BITSETC语言头文件 BITSETC语言头文件 BITSETC语言头文件 BITSETC...
本资源附件中实现了一个动态Bitset,和标准bitset兼容。 /** @defgroup Bitset Bitset位集类 * @{ */ //根据std::bitset改写,函数意义和std::bitset保持一致 class CORE_API Bitset: public Serializable { ...
acm相关资料vector、bitset、大数乘法等等
文档模仿STL库的BITSET写的一个bitset,但是和STL不同的是这个类是一个可以动态扩展的,使用方法和STL的类似,可以参考STL使用
bitset - Go包实现 bitsets
基于JDK1.8的BitSet 源码分析, 描述了实现的原理 个方法的含义 虽然没有写出实际的测试代码 但是只要是细度了我的这个分析 在使用的时候就不是问题了
自己实现的bitset数据结构,在vs2005下编译通过。有测试成素。
主要介绍了Java编程中的HashSet和BitSet详解的相关资料,需要的朋友可以参考下
C++的 bitset 在 bitset 头文件中,它是一种类似数组的结构,它的每一个元素只能是0或1,每个元素仅用1bit空间。 下面是具体用法 构造函数 bitset常用构造函数有四种,如下 bitset<4> bitset1; //无参构造,...
布隆过滤器 字符串比较 KMP 算法 深度优先、广度优先 贪心算法 回溯算法 剪枝算法 动态规划 朴素贝叶斯 推荐算法 最小生成树算法 最短路径算法 并发 Java 并发 多线程 线程安全 一致性、事务 事务 ACID 特性 事务的...
使用C++编写的遗传算法,代码量200行左右,供大家学习研究,互相交流。
C++下的bitset,强大而简单的位运算功能,象使用数组一样对位进行操作
和vector对象不一样的是bitset类型对象的区别仅在其长度而不在其类型。在定义bitset的时候,要明确bitset包含了多少位,须在尖括号内给出它的长度值。长度值必须定义为整形字面值常量或是已用常量值初始化的整型的...