【随笔记】Redis(三)布隆过滤器BloomFilter
2021/5/7 19:28:57
本文主要是介绍【随笔记】Redis(三)布隆过滤器BloomFilter,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
【随笔记】Redis(三)布隆过滤器BloomFilter
由简入繁,水滴石穿。
BloomFilter
它是一个很长的二进制向量和一系列随机映射函数,主要用于检索一个元素是否在一个集合内。优点很明显,就是空间效率和查询时间都比其他的算法快,缺点同样明显,就是有误识别率和删除困难。
例如:当一个元素X{a,b,c,d,e}加入集合,每个元素通过K各Hash函数将这个元素映射成一个阵列(Bit array)中的K个点,并把他们置为1.检索的时候我们只需要看这些K点是不是都等于1就可以知道集合中有没有这个元素了。如果这些K点的任何一个是0,那么这个被检索的元素一定不在,如果都是1,则元素可能在。
从上面的例子可以看出,BloomFilter能判断出f可能存在,但是无法判断出f一定存在,这就是误识别率;
但是很多时候我们在实际使用中,不需要知道这个元素一定存在,更多的是需要判断出这个元素一定不在,例如防止雪崩这件事,就是需要判断出g一定不在。
BloomFilter 的缺点
就像上面的例子一样,之所以能再去时间上和空间上效率特别高,它牺牲的是准确性和删除的便利性。
- 误判:就像上面例子中f元素一样,他的几个K值位置都是1,所以就会误判存在。
- 删除困难:一个放入容器的元素映射到bit数组的K个位置上是1,删除的时候不能简单的直接置为0,因为还有其他的元素。
guava实现布隆过滤器
- 引入Guava包
<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>23.0</version> </dependency>
- 用例
public class TestBloomFilter { private static int total = 1000000; private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total); public static void main(String[] args) { // 初始化1000000条数据到过滤器中 for (int i = 0; i < total; i++) { bf.put(i); } // 匹配已在过滤器中的值,是否有匹配不上的 for (int i = 0; i < total; i++) { if (!bf.mightContain(i)) { System.out.println("有坏人逃脱了~~~"); } } // 匹配不在过滤器中的10000个值,有多少匹配出来 int count = 0; for (int i = total; i < total + 10000; i++) { if (bf.mightContain(i)) { count++; } } System.out.println("误伤的数量:" + count); } }
错误率越大,所需要的空间和时间就越小,反之错误率越小,需要的空间和时间就越大。
所以BloomFilter的实现在于对错误率的容忍程度,可以在过滤一些非常规的请求,垃圾短信,垃圾邮件等场景使用。
这篇关于【随笔记】Redis(三)布隆过滤器BloomFilter的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31Tiny RDM:你的下一代Redis桌面GUI神器-icode9专业技术文章分享
- 2024-03-21redisinsight-v2
- 2024-02-26Typed property App\Api\Mapper\GamePropsConfigMapper::$apiRedis must not be accessed before initia-icode9专业技术文章分享
- 2024-02-21redisson getlock
- 2024-02-20redis config
- 2024-02-20redis leaderboard
- 2024-01-23缓存选型:Redis or MemCache
- 2024-01-22面试官:Redis持久化能关吗?怎么关?
- 2024-01-21Redis压测工具redis-benchmark-icode9专业技术文章分享
- 2024-01-19这才是你应该了解的Redis数据结构!