基于PHP布隆过滤器的容错与误报率优化技巧探讨

$key = 'example_key';
$hash1 = crc32($key) % $bitArraySize;
$hash2 = fnv1a32($key) % $bitArraySize;
$hash3 = murmurhash3($key) % $bitArraySize;

class BloomFilter {
    private $bitArray;
    private $bitArraySize;
    private $elementCount;
    private $expectedFalsePositiveRate;

    public function __construct($expectedElements, $errorRate) {
        $this->expectedFalsePositiveRate = $errorRate;
        $this->bitArraySize = $this->calculateBitArraySize($expectedElements, $errorRate);
        $this->bitArray = array_fill(0, $this->bitArraySize, 0);
        $this->elementCount = 0;
    }

    public function add($key) {
        // 添加元素逻辑
        // ...
        $this->elementCount++;
        if ($this->elementCount / $this->bitArraySize > $this->expectedFalsePositiveRate) {
            $this->resizeBitArray();
        }
    }

    private function resizeBitArray() {
        // 动态扩容逻辑
        // ...
    }

    // 其他方法省略
}

function fnv1a32($key) {
    $fnv_prime = 16777619;
    $fnv_offset_basis = 2166136261;
    $hash = $fnv_offset_basis;
    $keyLength = strlen($key);
    for ($i = 0; $i < $keyLength; $i++) {
        $hash ^= ord($key[$i]);
        $hash *= $fnv_prime;
    }
    return $hash;
}