Struktur data PHP: penggunaan penapis Bloom yang bijak untuk mencapai perolehan koleksi yang cekap

Penapis Bloom ialah struktur data yang cekap ruang yang digunakan untuk menentukan sama ada sesuatu elemen tergolong dalam set. Ia menggunakan fungsi cincang dan tatasusunan sedikit untuk mencari dengan cekap jika elemen itu ada, mungkin dengan positif palsu. Ia sesuai untuk senario di mana sejumlah besar elemen perlu diambil dengan cepat, seperti pengesanan pendua URL.

Struktur data PHP: Gunakan penapis Bloom dengan bijak untuk mencapai perolehan koleksi yang cekap

Pengenalan

Penapis Bloom ialah struktur data yang sangat cekap ruang yang digunakan untuk menentukan sama ada sesuatu elemen tergolong Ia menggunakan fungsi cincang dan tatasusunan bit untuk mencari dengan cekap sama ada unsur itu hadir.

Prinsip

Penapis Bloom memulakan tatasusunan sedikit, dan setiap kedudukan pada mulanya adalah 0. Kemudian, elemen dicincang menggunakan berbilang fungsi cincang, tatasusunan bit diindeks dengan nilai cincang, dan nilai pada kedudukan itu ditetapkan kepada 1.

Jika elemen tergolong dalam set, nilai cincangnya akan menemui sekurang-kurangnya satu kedudukan dalam tatasusunan bit iaitu 1. Walau bagaimanapun, ia juga mungkin untuk mencari kedudukan 1 untuk elemen yang tidak tergolong dalam set, dipanggil positif palsu.

Pelaksanaan

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;
    }
}

Kes praktikal: Kesan pendua URL

Matlamat: Gunakan penapis Bloom untuk mengesan dengan cepat sama ada sejumlah besar URL telah dirangkak.

Pelaksanaan:

1. Memulakan penapis Bloom, set saiz dan bilangan fungsi cincang.
2. Panggil kaedah add() untuk setiap URL yang dirangkak untuk menambahkannya pada penapis. add() 方法将其添加到过滤器中。
3. 当遇到新的 URL 时，使用 isExists()
Apabila menemui URL baharu, gunakan kaedah isExists() untuk menyemak dengan cepat sama ada URL itu sudah wujud dalam penapis. Jika ia wujud, URL dilangkau jika tidak, URL baharu ditambahkan pada penapis.

Kelebihan:

• Space efficient: Saiz penapis Bloom tiada kaitan dengan bilangan elemen yang perlu dikesan.
• Pendapatan pantas: Dengan menggunakan fungsi cincang, operasi mendapatkan semula tidak memerlukan merentasi keseluruhan koleksi.
• Kadar ralat yang boleh diterima: Penapis Bloom membenarkan beberapa positif palsu, tetapi saiz dan bilangan fungsi cincang boleh dilaraskan mengikut keperluan untuk mengoptimumkan kadar ralat.

🎜

Atas ialah kandungan terperinci Struktur data PHP: penggunaan penapis Bloom yang bijak untuk mencapai perolehan koleksi yang cekap. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!