甘肃网站建设方案服务至上,怎么做网站子页,计算机培训班有哪些,企业电话名录介绍布隆过滤器#xff08;Bloom Filter#xff09;是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多#xff0c;缺点是有一定的误识别率… 介绍布隆过滤器Bloom Filter是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多缺点是有一定的误识别率和删除困难。优点:相比于其他数据结构, 布隆过滤器在时间和空间方面都有巨大的优势(都是常数)缺点:有一定的误识别率(布隆过滤器报告 元素在集合中, 而实际并不存在), 但不会错误识别(元素确实不存在于集合中, 布隆过滤器不会报告存在于集合中)删除困难开发定时任务每隔几个小时自动创建一个新的布隆过滤器数组替换老的基本概念如果想要判断一个元素是不是在一个集合里一般想到的是将所有元素保存起来然后通过比较确定。链表树等等数据结构都是这种思路. 但是随着集合中元素的增加我们需要的存储空间越来越大检索速度也越来越慢(O(n),O(logn))。不过世界上还有一种叫作散列表又叫哈希表Hash table的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列Bit array中的一个点。这样一来我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。Hash面临的问题就是冲突。假设Hash函数是良好的如果我们的位阵列长度为m个点那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m / 100个元素。显然这就不叫空间效率了Space-efficient了。解决方法也简单就是使用多个Hash如果它们有一个说元素不在集合中那肯定就不在。如果它们都说在虽然也有一定可能性它们在说谎不过直觉上判断这种事情的概率是比较低的。应用场景解决缓存穿透网页爬虫对URL的去重避免爬取相同的URL地址反垃圾邮件从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱c#使用布隆过滤器https://github.com/vla/BloomFilter.NetCorepublic class Demo{static IBloomFilter bf FilterRedisBuilder.Build(localhost, InstanceName, 5000000, 0.001);public void Sample(){bf.Add(Value);Console.WriteLine(bf.Contains(Value));}}var services new ServiceCollection();
services.AddBloomFilter(setupAction
{setupAction.UseRedis(new FilterRedisOptions{Name Redis1,RedisKey BloomFilter1,Endpoints new[] { localhost }.ToList()});
});var provider services.BuildServiceProvider();
var bf provider.GetServiceIBloomFilter();
bf.Add(Value);
Console.WriteLine(bf.Contains(Value));ExpectedElements 1000000
ErrRate 1%BenchmarkDotNetv0.12.1, OSWindows 10.0.19042
AMD Ryzen 7 5800X, 1 CPU, 16 logical and 8 physical cores
.NET Core SDK5.0.203[Host] : .NET Core 5.0.6 (CoreCLR 5.0.621.22011, CoreFX 5.0.621.22011), X64 RyuJITDefaultJob : .NET Core 5.0.6 (CoreCLR 5.0.621.22011, CoreFX 5.0.621.22011), X64 RyuJIT
