Bagaimana untuk menggunakan penapis Bloom di Java

Apakah itu penapis Bloom

Penapis Bloom ialah struktur data rawak yang sangat cekap ruang yang menggunakan tatasusunan bit (BitSet) untuk mewakili set dan menghantar nombor tertentu Fungsi cincang memetakan elemen ke kedudukan dalam tatasusunan bit dan digunakan untuk menyemak sama ada sesuatu elemen tergolong dalam set ini.

Idea teras pelaksanaan

Untuk elemen, berbilang nilai cincang dihasilkan melalui berbilang fungsi cincang, dan bit yang sepadan ditetapkan kepada 1 dalam tatasusunan bit adalah berbilang cincangan Jika bit nilai yang sepadan adalah semua 1, elemen itu mungkin berada dalam set jika sekurang-kurangnya satu bit nilai cincang yang sepadan ialah 0, elemen itu pastinya tiada dalam set. Kaedah ini boleh mencapai carian yang cekap dalam ruang yang lebih kecil, tetapi mungkin mempunyai kadar positif palsu.

Cara memahami

Penapis Bloom biasa mengandungi tiga parameter: saiz tatasusunan bit (iaitu bilangan elemen yang disimpan); kadar positif), iaitu nisbah bilangan elemen kepada saiz tatasusunan bit.

Seperti yang ditunjukkan dalam rajah di atas: Proses operasi asas penapis Bloom termasuk memulakan tatasusunan bit dan fungsi cincang, memasukkan elemen, menyemak sama ada elemen berada dalam set , dsb. Antaranya, setiap elemen akan dipetakan kepada berbilang kedudukan dalam tatasusunan bit oleh pelbagai fungsi cincang Apabila menyemak sama ada elemen itu berada dalam set, anda perlu memastikan bahawa semua bit yang sepadan ditetapkan kepada 1 sebelum dianggap bahawa elemen itu mungkin. berada dalam set dalam koleksi.

Senario aplikasi biasa

Penapisan spam: Tetapkan nilai cincang yang sepadan bagi semua e-mel senarai hitam kepada 1 dalam penapis Bloom Untuk setiap e-mel baharu, semak sama ada nilai cincangnya dalam kedudukan yang sepadan dalam penapis Bloom ialah 1. Jika ya, e-mel itu dianggap sebagai spam, jika tidak, ia mungkin e-mel biasa

Penyahduplikasi URL: Tetapkan kedudukan yang sepadan bagi; nilai cincang URL yang dirangkak dalam penapis Bloom kepada 1. Untuk setiap URL baharu, tetapkan nilai cincangnya dalam penapis Bloom Periksa sama ada kedudukan yang sepadan adalah semua 1. Jika ya, URL itu dianggap telah dirangkak, sebaliknya ia perlu dirangkak;

Pecahan cache: Sepadan dengan semua data yang ada dalam cache Kedudukan nilai cincang yang sepadan dalam penapis Bloom ditetapkan kepada 1. Untuk setiap nilai kunci pertanyaan , semak sama ada nilai cincangnya dalam kedudukan yang sepadan dalam penapis Bloom adalah semua 1. Jika ya, ia dianggap Nilai kunci wujud dalam cache, jika tidak, ia perlu disoal daripada pangkalan data dan ditambah pada cache.

Perlu diambil perhatian bahawa kadar positif palsu penapis Bloom akan berkurangan apabila saiz tatasusunan bit meningkat, tetapi ia juga akan meningkatkan overhed memori dan masa pengiraan. Untuk memudahkan pemahaman tentang penapis Bloom, yang berikut menggunakan kod java untuk melaksanakan penapis Bloom yang mudah:

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;

  }

}

Atas ialah kandungan terperinci Bagaimana untuk menggunakan penapis Bloom di Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!