参考
git clone https://github.com/jxnu-liguobin/Scala-BloomFilter
cd Scala-BloomFilter/
gradle clean build
要创建一个空的Bloom过滤器,只需使用所期望的假阳性概率和希望添加到Bloom过滤器中的元素个数来创建ScalaBloomFilter类的实例
val elementCount: Int = 50000 // 测试元素个数
val falsePositiveProbability: Double = 0.001 //假阳性概率
val bf = new ScalaBloomFilter[String](falsePositiveProbability, elementCount)
在创建了Bloom过滤器之后,可以使用add()方法添加新元素
bf.add("test")
若要检查某个元素是否已存储在Bloom过滤器中,可以使用contains()方法
bf.contains("test"); // returns true
一个完整的例子
val elementCount: Int = 50000 // 测试元素个数
val falsePositiveProbability: Double = 0.001 //假阳性概率
val bf = new ScalaBloomFilter[String](falsePositiveProbability, elementCount)
bf.add("test")
if (bf.contains("test")) {
println("存在元素: test")
println("根据公式计算假阳性的预期概率: " + bf.expectedFalsePositiveProbability)
}
if (bf.contains("test1")) {
System.out.println("There was a test1.")
}
讲述布隆过滤器的原理之前,我们先思考一下,通常你判断某个元素是否存在用的是什么?应该蛮多人回答 HashMap 吧,确实可以将值映射到 HashMap 的 Key,然后可以在 O(1) 的时间复杂度内返回结果,效率奇高。 但是 HashMap 的实现也有缺点,例如存储容量占比高,考虑到负载因子的存在,通常空间是不能被用满的,而一旦你的值很多例如上亿的时候,那 HashMap 占据的内存大小就变得很可观了。 还比如说你的数据集存储在远程服务器上,本地服务接受输入,而数据集非常大不可能一次性读进内存构建 HashMap 的时候,也会存在问题。
作者:YoungChen__
链接:https://www.jianshu.com/p/2104d11ee0a2
来源:简书
简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。
布隆过滤器是一个 bit 向量或者说 bit 数组。
随着增加的值越来越多,被置为 1 的 bit 位也会越来越多,这样某个值 “taobao” 即使没有被存储过,但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ,那么程序还是会判断 “taobao” 这个值存在。
因为bit位被两个值共同覆盖的话,一旦你删除其中一个值而将其置位 0,那么下次判断另一个值例是否存在的话,会直接返回 false,而实际上你并没有删除它。
计数删除。但是计数删除需要存储一个数值,而不是原先的 bit 位,会增大占用的内存大小。这样的话,增加一个值就是将对应索引槽上存储的值加一,删除则是减一,判断是否存在则是看值是否大于0。
过小的布隆过滤器很快所有的 bit 位均为 1,那么查询任何值都会返回“可能存在”,起不到过滤的目的了。布隆过滤器的长度会直接影响误报率,布隆过滤器越长其误报率越小。 另外,哈希函数的个数也需要权衡,个数越多则布隆过滤器 bit 位置位 1 的速度越快,且布隆过滤器的效率越低;但是如果太少的话,那我们的误报率会变高。
Redis 因其支持 setbit 和 getbit 操作,且纯内存性能高等特点,因此天然就可以作为布隆过滤器来使用。但是布隆过滤器的不当使用极易产生大 Value,增加 Redis 阻塞风险,因此生成环境中建议对体积庞大的布隆过滤器进行拆分。 拆分的形式方法多种多样,但是本质是不要将 Hash(Key) 之后的请求分散在多个节点的多个小 bitmap 上,而是应该拆分成多个小 bitmap 之后,对一个 Key 的所有哈希函数都落在这一个小 bitmap 上。
一般的解决思路是两个,一是存储原始数据,当 bf 超过 1000 个元素后生成一个 2000 个元素的 bf,另一种是堆叠 bf (叫做 scalable bloomfilter),超过 1000 个元素后再生成一个新的 1000 容量的 bf,查询的时候查多个。
Sign in for post a comment
Comments ( 0 )