PHP-Datenstruktur: Cleverer Einsatz von Bloom-Filtern, um einen effizienten Sammlungsabruf zu erreichen

Der Bloom-Filter ist eine platzsparende Datenstruktur, mit der bestimmt wird, ob ein Element zu einer Menge gehört. Es verwendet eine Hash-Funktion und ein Bit-Array, um effizient herauszufinden, ob das Element vorhanden ist, möglicherweise mit falsch positiven Ergebnissen. Es eignet sich für Szenarien, in denen eine große Anzahl von Elementen schnell abgerufen werden muss, z. B. bei der Erkennung doppelter URLs.

PHP-Datenstruktur: Verwenden Sie Bloom-Filter geschickt, um einen effizienten Sammlungsabruf zu erreichen

Einführung

Ein Bloom-Filter ist eine äußerst platzsparende Datenstruktur, mit der bestimmt wird, ob ein Element zu einer Sammlung gehört. Es verwendet eine Hash-Funktion und ein Bit-Array, um effizient herauszufinden, ob das Element vorhanden ist.

Prinzip

Der Bloom-Filter initialisiert ein Bit-Array und jede Position ist zunächst 0. Anschließend werden die Elemente mithilfe mehrerer Hash-Funktionen gehasht, das Bit-Array wird mit dem Hash-Wert indiziert und der Wert an dieser Position wird auf 1 gesetzt.

Wenn ein Element zur Menge gehört, findet sein Hashwert mindestens eine Position im Bitarray, die 1 ist. Es ist jedoch auch möglich, die Position 1 für ein Element zu finden, das nicht zur Menge gehört, was als falsch positiv bezeichnet wird.

Implementierung

class BloomFilter {

    // 过滤器大小 (位数)
    private $size;

    // 哈希函数个数
    private $numHashes;

    // 哈希函数
    private $hashFunctions;

    // 过滤器位数组
    private $filter;

    // 初始化布隆过滤器
    public function __construct($size, $numHashes) {
        $this->size = $size;
        $this->numHashes = $numHashes;
        $this->initHashFunctions();
        $this->filter = array_fill(0, $this->size, 0);
    }

    // 初始化哈希函数
    private function initHashFunctions() {
        $this->hashFunctions = [];
        for ($i = 0; $i < $this->numHashes; $i++) {
            $this->hashFunctions[] = function ($key) use ($i) {
                return abs(crc32($key . $i));
            };
        }
    }

    // 向过滤器中添加元素
    public function add($element) {
        foreach ($this->hashFunctions as $hashFunction) {
            $index = $hashFunction($element) % $this->size;
            $this->filter[$index] = 1;
        }
    }

    // 检查元素是否存在过滤器中
    public function isExists($element) {
        foreach ($this->hashFunctions as $hashFunction) {
            $index = $hashFunction($element) % $this->size;
            if ($this->filter[$index] == 0) {
                return false;
            }
        }
        // 找到了元素的所有哈希值对应的位，但可能是假阳性
        return true;
    }
}

Praxisfall: URL-Duplikate erkennen

Ziel: Verwenden Sie den Bloom-Filter, um schnell zu erkennen, ob eine große Anzahl von URLs gecrawlt wurde.

Implementierung:

1. Bloom-Filter initialisieren, Größe und Anzahl der Hash-Funktionen festlegen.
2. Rufen Sie die Methode add() für jede gecrawlte URL auf, um sie dem Filter hinzuzufügen. add() 方法将其添加到过滤器中。
3. 当遇到新的 URL 时，使用 isExists()
Wenn Sie auf eine neue URL stoßen, verwenden Sie die Methode isExists(), um schnell zu überprüfen, ob sie bereits im Filter vorhanden ist. Wenn sie vorhanden ist, wird die URL übersprungen; andernfalls wird die neue URL zum Filter hinzugefügt.

Vorteile:

• Platzsparend: Die Größe des Bloom-Filters hat nichts mit der Anzahl der Elemente zu tun, die erkannt werden müssen.
• Schneller Abruf: Durch die Verwendung von Hash-Funktionen ist für Abrufvorgänge nicht das Durchlaufen der gesamten Sammlung erforderlich.
• Akzeptable Fehlerrate: Bloom-Filter erlauben einige Fehlalarme, aber die Größe und Anzahl der Hash-Funktionen können nach Bedarf angepasst werden, um die Fehlerrate zu optimieren.

🎜

Das obige ist der detaillierte Inhalt vonPHP-Datenstruktur: Cleverer Einsatz von Bloom-Filtern, um einen effizienten Sammlungsabruf zu erreichen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!