布隆过滤器总结

[系列] Go 使用 defer 函数 要注意的几个点

一:布隆过滤器简介:

  Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom Filter通过极少的错误换取了存储空间的极大节省。

二:优势和劣势

1:优势:

①:仅仅保留数据的指纹信息,空间效率极高

②:信息安全性极高

③:查询效率极高,时间复杂度为O(N)

2:劣势 :

AQS系列(六)- Semaphore的使用及原理

①:存在一定的误判

②:删除数据困难

三:常用API总结:

引入Google的guava java API包,常用方法有:create(Funnel<? super T> funnel, int expectedInsertions, double fpp); put(T object); mightContain(T object) ; 

四:使用场景: 

  布隆过滤器在redis集群的上一步,主要是判断数据是否存在于布隆过滤器中,这样减少对redis服务器的压力。布隆过滤器其原理就是把大数据量加载到内存中,判断数据是否存在。大数据量加载到内存中,这样容易导致OOM。一般是在应用启动的时候,进行初始化把数据加载到布隆过滤器中。布隆过滤器所需要占内存公式为:设bit数组大小为m,样本数量为n,失误率为p。由题可知 n = 500万,p = 3%(Google布隆过滤器默认为3%,我们也可以修改),公式为:

布隆过滤器总结

五:与redis服务器集成:

 

黑匣子

© 版权声明
THE END
喜欢就支持一下吧
点赞0
分享