bloom filter
2017-03-12 16:52:53 0 举报布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。因此通常用在大数据量的情况下，判断某个元素是否可能属于一个集合。
作者其他创作
大纲/内容
0
h3(e)
1
Cursor：0，key=BF-0
hash2
hash1
hash3
e
h1(c)
m=28
h2(b)
h3(b)
B
h3(c)
h2(d)
n=3
for x in S for i in {1..3} B[hi(x)]=1;
一定不在集合S中
Cursor：n，key=BF-n
h3(a)
可能在集合S中，也可能不在
a
Cursor：1，key=BF-1
h1(b)
h2(a)
h3(d)
c
h2(e)
for i in {1..3} if B[hi(x)]==0 return false;return true;
b
d
h1(d)
h2(c)
S
h1(e)
A
……
h1(a)
职业：暂无
0 条评论
下一页
