So wenden Sie den Bloom-Filter in Java an

Was ist ein Bloom-Filter?

Ein Bloom-Filter ist eine sehr platzsparende Zufallsdatenstruktur, die ein Bit-Array (BitSet) zur Darstellung einer Menge verwendet und die Elemente durch eine bestimmte Anzahl von Hash-Funktionen einer Position zuordnet ein Bit-Array, mit dem überprüft wird, ob ein Element zu dieser Menge gehört.

Die Kernidee der Implementierung

Für ein Element werden mehrere Hash-Werte durch mehrere Hash-Funktionen generiert und die entsprechenden Bits im Bit-Array auf 1 gesetzt sind alle 1. Es wird davon ausgegangen, dass das Element möglicherweise in der Menge enthalten ist. Wenn mindestens ein entsprechendes Bit des Hash-Werts 0 ist, darf das Element nicht in der Menge enthalten sein. Mit dieser Methode kann eine effiziente Suche auf kleinerem Raum erreicht werden, es kann jedoch zu einer Falsch-Positiv-Rate kommen.

Wie ist das zu verstehen? Ein typischer Bloom-Filter enthält drei Parameter: die Größe des Bit-Arrays (d. h. die Anzahl der gespeicherten Elemente); den Füllfaktor (d. h. die Falsch-Positiv-Rate); , also die Anzahl der Elemente im Verhältnis zur Größe des Bitarrays.

Wie im Bild oben gezeigt: Der grundlegende Betriebsprozess des Bloom-Filters umfasst das Initialisieren des Bit-Arrays und der Hash-Funktion, das Einfügen von Elementen, das Überprüfen, ob die Elemente im Satz enthalten sind usw. Unter diesen wird jedes Element durch mehrere Hash-Funktionen mehreren Positionen im Bit-Array zugeordnet. Wenn Sie prüfen, ob das Element in der Menge vorhanden ist, müssen Sie sicherstellen, dass alle entsprechenden Bits auf 1 gesetzt sind, bevor davon ausgegangen wird, dass das Element möglicherweise vorhanden ist im Set in der Sammlung sein.

Typisches Anwendungsszenario

Spam-Filterung

: Setzen Sie den entsprechenden Hashwert aller Blacklist-E-Mails im Bloom-Filter auf 1. Stellen Sie für jede neue E-Mail deren Hashwert ein. Überprüfen Sie, ob die entsprechenden Positionen im Bloom-Filter alle 1 sind . Wenn ja, wird die E-Mail als Spam betrachtet, andernfalls handelt es sich um eine normale E-Mail Überprüfen Sie bei jeder neuen URL, ob der Hashwert an der entsprechenden Position im Bloom-Filter 1 ist. Wenn ja, gilt die URL als gecrawlt.

Cache-Aufschlüsselung

: Legen Sie den entsprechenden Hash fest Der Wert aller Daten im Cache wird im Bloom-Filter auf 1 gesetzt und der Schlüsselwert jeder Abfrage wird gehasht. Überprüfen Sie, ob die entsprechenden Positionen der Hash-Werte im Bloom-Filter alle 1 sind. Wenn ja, wird der Schlüsselwert berücksichtigt Andernfalls muss es aus der Datenbank abgefragt und dem Cache hinzugefügt werden. Es ist zu beachten, dass die Falsch-Positiv-Rate des Bloom-Filters mit zunehmender Bit-Array-Größe abnimmt, aber auch der Speicheraufwand und die Berechnungszeit steigen. Um das Verständnis von Bloom-Filtern zu erleichtern, wird im Folgenden Java-Code verwendet, um einen einfachen Bloom-Filter zu implementieren:

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;

  }

}

Das obige ist der detaillierte Inhalt vonSo wenden Sie den Bloom-Filter in Java an. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!