Java中的佈隆過濾器你真的懂瞭嗎

Posted on by

什麼是佈隆過濾器

佈隆過濾器（Bloom Filter）是一種空間效率非常高的隨機數據結構，它利用位數組（BitSet）表示一個集合，並通過一定數量的哈希函數將元素映射為位數組中的位置，用於檢查一個元素是否屬於這個集合。

實現的核心思想

對於一個元素，通過多個哈希函數生成多個哈希值，將對應的位在位數組中設為 1，若多個哈希值對應的位都為 1，則認為該元素可能在集合中；若至少有一個哈希值對應的位為 0，則該元素一定不在集合中。這種方法可以在較小的空間中實現高效的查找，但可能存在誤判率（false positive）。

怎麼理解

一個典型的佈隆過濾器包含三個參數： 位數組的大小（即存儲元素的個數）； 哈希函數的個數； 填充因子（即誤判率），即將元素數量與位數組大小的比值。

如上圖所示： 佈隆過濾器的基本操作流程，包括初始化位數組和哈希函數、插入元素、檢查元素是否在集合中等。其中，每個元素都會被多個哈希函數映射到位數組中的多個位置，而在檢查元素是否在集合中時，需要確保所有對應的位都被設置為 1，才會認為該元素可能在集合中。

典型應用場景

垃圾郵件過濾： 將所有的黑名單郵件對應的哈希值在佈隆過濾器中對應的位置設為 1，對於每一封新郵件，將其哈希值在佈隆過濾器中對應的位置檢查是否都為 1，若是，則認為該郵件是垃圾郵件，否則可能是正常郵件；

URL 去重： 將已經抓取的 URL 對應的哈希值在佈隆過濾器中對應的位置設為 1，對於每一條新的 URL，將其哈希值在佈隆過濾器中對應的位置檢查是否都為 1，若是，則認為該 URL 已經抓取過，否則需要進行抓取；

緩存擊穿： 將緩存中存在的所有數據對應的哈希值在佈隆過濾器中對應的位置設為 1，對於每一個查詢的鍵值，將其哈希值在佈隆過濾器中對應的位置檢查是否都為 1，若是，則認為該鍵值存在於緩存中，否則需要從數據庫中查詢並將其添加到緩存中。

需要註意的是，佈隆過濾器的誤判率會隨著位數組大小的增加而減小，但同時也會增加內存開銷和計算時間。 為瞭方便理解佈隆過濾器，下面用java代碼實現一個簡單的佈隆過濾器：

import java.util.BitSet;
import java.util.Random;
public class BloomFilter {
  private BitSet bitSet;           // 位集，用於存儲哈希值
  private int bitSetSize;         // 位集大小
  private int numHashFunctions;   // 哈希函數數量
  private Random random;          // 隨機數生成器
  // 構造函數，根據期望元素數量和錯誤率計算位集大小和哈希函數數量
  public BloomFilter(int expectedNumItems, double falsePositiveRate) {
    this.bitSetSize = optimalBitSetSize(expectedNumItems, falsePositiveRate);
    this.numHashFunctions = optimalNumHashFunctions(expectedNumItems, bitSetSize);
    this.bitSet = new BitSet(bitSetSize);
    this.random = new Random();
  }
  // 根據期望元素數量和錯誤率計算最佳位集大小
  private int optimalBitSetSize(int expectedNumItems, double falsePositiveRate) {
    int bitSetSize = (int) Math.ceil(expectedNumItems * (-Math.log(falsePositiveRate) / Math.pow(Math.log(2), 2)));
    return bitSetSize;
  }
  // 根據期望元素數量和位集大小計算最佳哈希函數數量
  private int optimalNumHashFunctions(int expectedNumItems, int bitSetSize) {
    int numHashFunctions = (int) Math.ceil((bitSetSize / expectedNumItems) * Math.log(2));
    return numHashFunctions;
  }
  // 添加元素到佈隆過濾器中
  public void add(String item) {
    // 計算哈希值
    int[] hashes = createHashes(item.getBytes(), numHashFunctions);
    // 將哈希值對應的位設置為 true
    for (int hash : hashes) {
      bitSet.set(Math.abs(hash % bitSetSize), true);
    }
  }
  // 檢查元素是否存在於佈隆過濾器中
  public boolean contains(String item) {
    // 計算哈希值
    int[] hashes = createHashes(item.getBytes(), numHashFunctions);
    // 檢查哈希值對應的位是否都為 true
    for (int hash : hashes) {
      if (!bitSet.get(Math.abs(hash % bitSetSize))) {
        return false;
      }
    }
    return true;
  }
  // 計算給定數據的哈希值
  private int[] createHashes(byte[] data, int numHashes) {
    int[] hashes = new int[numHashes];
    int hash1 = Math.abs(random.nextInt());
    int hash2 = Math.abs(random.nextInt());
    for (int i = 0; i < numHashes; i++) {
      // 使用兩個隨機哈希函數計算哈希值
      hashes[i] = Math.abs((hash1 * i) + (hash2 * i) + i) % data.length;
    }
    return hashes;
  }
}

以上就是Java中的佈隆過濾器你真的懂瞭嗎的詳細內容，更多關於Java佈隆過濾器的資料請關註WalkonNet其它相關文章！

推薦閱讀：