PHP 데이터 구조: Bloom 필터를 영리하게 사용하여 효율적인 컬렉션 검색 달성-PHP 튜토리얼-php.cn

PHP 데이터 구조: Bloom 필터를 영리하게 사용하여 효율적인 컬렉션 검색 달성

WBOY

풀어 주다： 2024-06-01 16:04:05

원래의

937명이 탐색했습니다.

블룸 필터는 요소가 집합에 속하는지 여부를 결정하는 데 사용되는 공간 효율적인 데이터 구조입니다. 해시 함수와 비트 배열을 사용하여 요소가 존재하는지(오탐 가능성이 있음) 효율적으로 찾습니다. URL 중복 감지와 같이 많은 수의 요소를 신속하게 검색해야 하는 시나리오에 적합합니다.

PHP 데이터 구조: Bloom 필터를 영리하게 사용하여 효율적인 컬렉션 검색 달성

PHP 데이터 구조: Bloom 필터를 영리하게 사용하여 효율적인 컬렉션 검색을 달성하세요

Introduction

Bloom 필터는 요소가 수집에 속하는지 여부를 결정하는 데 사용되는 매우 공간 효율적인 데이터 구조입니다. 해시 함수와 비트 배열을 사용하여 요소의 존재 여부를 효율적으로 찾습니다.

원리

블룸 필터는 비트 배열을 초기화하며 각 위치는 초기에 0입니다. 그런 다음 요소는 여러 해시 함수를 사용하여 해시되고 비트 배열은 해시 값으로 인덱싱되며 해당 위치의 값은 1로 설정됩니다.

요소가 집합에 속하는 경우 해당 해시 값은 비트 배열에서 1인 위치를 하나 이상 찾습니다. 그러나 집합에 속하지 않는 요소에 대해 위치 1을 찾는 것도 가능하며, 이를 거짓양성(false positive)이라고 합니다.

구현

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

로그인 후 복사

실용 사례: URL 중복 감지

목표: 블룸 필터를 사용하여 많은 수의 URL이 크롤링되었는지 빠르게 감지합니다.

구현: