祝大家有美好的一天。
我们开设了新课程
“开发人员算法” ，旨在提高他们对数据处理的各种结构和算法的了解，解决各种语言的代数问题和动态编程问题。 因此，今天我们分享了有关Java中Bloom过滤器操作的小注释。
引言在本文中，我们将研究Guava库中Bloom过滤器的结构。 Bloom过滤器是一种具有高效内存使用率的概率数据结构，我们可以用来回答问题“集合中的这个元素吗？”。
布隆过滤器
中没有错误的否定词 ，因此，如果它返回假，则可以100％确保该元素不在集合中。
但是，Bloom过滤器
可以返回假阳性 ，因此，当
返回true时，表示该元素确实在集合中的概率很高，但是概率不是100％。
要了解有关布隆过滤器操作的更多信息，请查阅
本指南。
Maven成瘾我们将使用Bloom过滤器的Guava实现，因此添加一个Guava依赖项
最新版本可以在
Maven Central中找到。
<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>22.0</version> </dependency>
为什么要使用布隆过滤器？布隆过滤器的设计既
经济又快速 。 使用它时，我们可以弄清
我们准备接受的错误肯定答案的
可能性 ，并且根据配置，Bloom过滤器将占用尽可能少的内存。
由于其经济性，即使有大量元素，布隆过滤器也很容易装入内存。 某些数据库（包括Cassandra和Oracle）在访问磁盘或缓存之前（例如，当收到对特定ID的请求时）使用此筛选器进行初始检查。
如果过滤器说没有ID，则数据库可能会停止处理请求并返回到客户端。 否则，查询将转到磁盘并返回找到的项目。
创建布隆过滤器假设我们要创建一个不超过500个整数的Bloom过滤器，并且将误报的可能性提高三倍（百分之一（0.01））。
为此，我们可以使用Guava库中的
BloomFilter类。 有必要将报告的元素数量转移到过滤器，以及期望的误报概率：
BloomFilter<Integer> filter = BloomFilter.create( Funnels.integerFunnel(), 500, 0.01);
现在将一些数字添加到过滤器中：
filter.put(1); filter.put(2); filter.put(3);
我们仅添加了三个元素，并确定了插入的最大数量-500，因此我们的Bloom过滤器应该给出相当准确的结果。 使用
mightContain()方法对其进行测试：
assertThat(filter.mightContain(1)).isTrue(); assertThat(filter.mightContain(2)).isTrue(); assertThat(filter.mightContain(3)).isTrue(); assertThat(filter.mightContain(100)).isFalse();
顾名思义，如果方法返回true，则我们不能100％确定此元素确实在过滤器中。
在我们的例子中，当
mightContain()返回true时，表示该元素在过滤器中的占99％，而结果为假阳性的占1％。 如果过滤器返回false，则可以100％确保该元素丢失。
过饱和的布隆过滤器设计布隆过滤器时，重要的是要为预期的元素数量提供足够准确的值。 否则，我们的过滤器返回误报的次数会比我们希望的要多得多。 考虑一个例子。
假设我们创建了一个过滤器，该过滤器的误报率等于1％，元素的预期数量等于5，但是我们插入了100,000个元素：
BloomFilter<Integer> filter = BloomFilter.create( Funnels.integerFunnel(), 5, 0.01); IntStream.range(0, 100_000).forEach(filter::put);
期望元素这么少，筛选器将占用很少的内存。
但是，在添加大量元素之后，滤波器将变得过饱和，并且产生假阳性结果的可能性比所需的百分之一更高。
请注意，即使对于我们先前未插入过滤器中的值，
mightContatin()方法也返回true。
结论在本快速教程中，我们使用Guava实现研究了Bloom过滤器数据结构的概率性质。
所有这些示例和代码段的实现都可以在
GitHub项目中找到。
这是一个Maven项目，因此导入和启动应该不会很困难。
结束我们一直在等待评论和问题，这些评论和问题像往常一样可以留在这里，并
在开放日里与课程老师
Mikhail Gorshkov进行交流 。