Java中的布隆過濾器怎麼應用

什麼是布隆過濾器

布隆過濾器（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 hash2 = Math.abs(random.nextInt());

    int hash3 = Math.abs(random.nextInt());

    for (int i = 0; i < numHashes; i++) {

      // 使用两个随机哈希函数计算哈希值

      hashes[i] = Math.abs((hash2 * i) + (hash3 * i) + i) % data.length;

    }

    return hashes;

  }

}

以上是Java中的布隆過濾器怎麼應用的詳細內容。更多資訊請關注PHP中文網其他相關文章！