背景介紹

????????在互聯網中，我們經常遇到需要在大量數據中判斷目標數據是否存在的情況。例如，在網絡爬蟲中，我們需要判斷某個網址是否已經被訪問過。為了實現這一功能，通常需要使用一個容器來存儲已訪問過的網址。如果將這些數據直接存儲在磁盤中，每次判斷都要進行磁盤查詢，這將導致大量的IO操作，效率較低。因此，我們希望將這些數據保存在內存中。在數據量較小的情況下，可以使用Redis來存儲這些數據。但是，當數據量超過上千萬時，將會消耗幾GB甚至幾十GB的內存空間。然而，對于僅需要記錄數據是否存在的情況而言，這樣使用大量內存顯然是浪費的。為了解決這個問題，我們可以使用布隆過濾器(Bloom Filter)。布隆過濾器是一種占用空間少且時間效率高的工具。

布隆過濾器介紹

布隆過濾器是一種空間效率極高的概率型數據結構，用于快速判斷一個元素是否可能存在于一個集合中。它的核心特點是以極小的存儲空間換取高效的查詢性能，但存在一定的誤判率（False Positive）。

核心原理

1. 位數組（Bit Array）

   • 布隆過濾器使用一個長度為m的二進制位數組（初始全為0）作為底層存儲

   • 例如：[0, 0, 0, 0, 0, 0, 0, 0]（m=8）

2. 多個哈希函數

   • 使用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是不在當前集合中的。

也是就說，布隆過濾器是可能存在誤判的，通俗點說就是假陽性。

關鍵特性

1. 沒有假陰性（False Negative）

   如果查詢返回"不存在"，則元素一定不在集合中

2. 存在假陽性（False Positive）

   可能誤判不存在的元素為存在（概率通常<1%）原因：不同元素的哈希位置可能重疊

3. 不支持元素刪除

   簡單的布隆過濾器無法安全刪除元素（會影響到其他元素）

使用樣例

依賴導入

        <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;}
}