布隆过滤器的原理及使用
背景介绍
在互联网中，我们经常遇到需要在大量数据中判断目标数据是否存在的情况。例如，在网络爬虫中，我们需要判断某个网址是否已经被访问过。为了实现这一功能，通常需要使用一个容器来存储已访问过的网址。如果将这些数据直接存储在磁盘中，每次判断都要进行磁盘查询，这将导致大量的IO操作，效率较低。因此，我们希望将这些数据保存在内存中。在数据量较小的情况下，可以使用Redis来存储这些数据。但是，当数据量超过上千万时，将会消耗几GB甚至几十GB的内存空间。然而，对于仅需要记录数据是否存在的情况而言，这样使用大量内存显然是浪费的。为了解决这个问题，我们可以使用布隆过滤器(Bloom Filter)。布隆过滤器是一种占用空间少且时间效率高的工具。
布隆过滤器介绍
布隆过滤器是一种空间效率极高的概率型数据结构，用于快速判断一个元素是否可能存在于一个集合中。它的核心特点是以极小的存储空间换取高效的查询性能，但存在一定的误判率（False Positive）。
核心原理
位数组（Bit Array）
布隆过滤器使用一个长度为m的二进制位数组（初始全为0）作为底层存储
例如：
[0, 0, 0, 0, 0, 0, 0, 0]（m=8）
多个哈希函数
使用k个不同的哈希函数（h₁, h₂, ..., hₖ）
每个函数都能将输入元素映射到位数组的某个位置
当一个元素被添加到集合中时，它会通过k个哈希函数映射到位数组中的m个位置，并将这些位置的值设置为 1。在检查元素是否在集合中时，检查这些位置是否全为 1。如果其中有任何一个位置为 0，则该元素一定不在集合中；如果所有位置均为 1，则该元素可能在集合中。
简单举例：
假设现在有3个哈希函数，和一个8位的bit数组。元素a和b，都经过三次哈希函数生成三个哈希值，并映射到位数组的不同的位置，并设置为1。元素a映射的位置是（0,3,7），元素b映射的位置是（2,5,7）.
如果一个元素c过来，我们检查它映射后的三个位置是否全是1，就可以判断元素C是否在当前集合中了。
其实我们可以发现，元素a和元素b映射的位置7都是1，也就是说，位置是可能重叠的。假设当前集合已经有a和b了，但是呢一个元素c过来，它映射的位置为（0,2,7），这时候，它的所有位置都是1，布隆过滤器是认为它可能在集合中，但是我们看到元素c是不在当前集合中的。
也是就说，布隆过滤器是可能存在误判的，通俗点说就是假阳性。
关键特性
没有假阴性（False Negative）
如果查询返回"不存在"，则元素一定不在集合中存在假阳性（False Positive）
可能误判不存在的元素为存在（概率通常<1%）原因：不同元素的哈希位置可能重叠不支持元素删除
简单的布隆过滤器无法安全删除元素（会影响到其他元素）
使用样例
依赖导入
<dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>30.1-jre</version> <!-- Use the latest version --></dependency>Java代码
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;public class BloomFilterIntersection {public static void main(String[] args) {// 生成两个测试数据集Set<Integer> set1 = generateRandomSet(1_000_000, 10000000);Set<Integer> set2 = generateRandomSet(1_000_000, 10000000);// 人为添加一些共同元素for (int i = 0; i < 1000; i++) {int commonElement = 20000000 + i;set1.add(commonElement);set2.add(commonElement);}System.out.println("集合1大小: " + set1.size());System.out.println("集合2大小: " + set2.size());// 使用布隆过滤器查找交集long startTime = System.currentTimeMillis();Set<Integer> intersection = findIntersection(set1, set2);long endTime = System.currentTimeMillis();System.out.println("检测到的交集元素数量: " + intersection.size());System.out.println("计算耗时: " + (endTime - startTime) + "ms");// 验证前10个交集元素System.out.println("\n前10个交集元素示例:");intersection.stream().limit(10).forEach(System.out::println);}/*** 使用布隆过滤器找出两个集合的交集* @param set1 第一个集合* @param set2 第二个集合* @return 两个集合的交集*/public static Set<Integer> findIntersection(Set<Integer> set1, Set<Integer> set2) {// 创建布隆过滤器，预计插入set1的大小，误判率1%//Funnel 是 Guava 提供的一个接口，用于 将对象转换为字节流（PrimitiveSink）BloomFilter<Integer> filter = BloomFilter.create(Funnels.integerFunnel(),set1.size(),0.01);// 将第一个集合的所有元素添加到布隆过滤器for (Integer item : set1) {filter.put(item);}// 检查第二个集合中的哪些元素可能在第一个集合中Set<Integer> possibleMatches = new HashSet<>();for (Integer item : set2) {if (filter.mightContain(item)) {possibleMatches.add(item);}}// 由于布隆过滤器可能有假阳性，需要二次验证Set<Integer> actualIntersection = new HashSet<>(set1);actualIntersection.retainAll(possibleMatches);return actualIntersection;}/*** 生成随机整数集合* @param size 集合大小* @param bound 随机数范围* @return 包含随机整数的集合*/private static Set<Integer> generateRandomSet(int size, int bound) {Set<Integer> set = new HashSet<>();Random random = new Random();while (set.size() < size) {set.add(random.nextInt(bound));}return set;}
}