Bloom Filter 是一種空間極其高效的概率型資料結構,用於判斷元素是否存在於大數據集合中,允許極低的誤判率(False Positive),但絕無漏判。本文從原理到 PHP 完整實現,詳細剖析其核心機制與工程權衡。
m 位的位陣列,初始全 0。k 個相互獨立的哈希函數,每個函數將元素映射到 [0, m-1] 範圍。k 個哈希值,將對應位置 1。k 個哈希值,若所有位均為 1 則「可能存在」,若有任一位為 0 則「一定不存在」。誤判率公式:(1 - e^(-kn/m))^k。通過調整 m(位陣列大小)與 k(哈希函數數量)平衡空間、速度與誤判率。
$set = array(1,2,3,4,5,6);
$bloomFilter = array_fill(0, 10, 0);
// 簡單映射:直接用值作為下標(僅示意)
foreach ($set as $key) {
$bloomFilter[$key] = 1;
}
// 查詢
echo isset($bloomFilter[9]) && $bloomFilter[9] ? '在集合中' : '不在集合中';
class Bloom_Filter {
private $hashFuncNum; // 哈希函數個數
private $spaceGroupNum; // 空間組數(分片)
private $hashSpaceAssoc; // 位陣列存儲
private $oneNum = 8; // 每字節 8 位
public function __construct($hash_func_num = 3, $space_group_num = 1) {
$maxLength = pow(2, 25); // 32MB per group
$binary = pack('C', 0);
$this->hashFuncNum = $hash_func_num;
$this->spaceGroupNum = $space_group_num;
for ($i = 0; $i < $space_group_num; $i++) {
$this->hashSpaceAssoc[$i] = str_repeat($binary, $maxLength);
}
// 預計算 2^n 用於哈希
$this->powArray = array();
for ($i = 0; $i < 32; $i++) $this->powArray[$i] = 1 << $i;
}
// 多哈希函數(簡易示例,實際建議用 murmurhash、fnv 等)
private function _hash($str, $seed) {
$hash = 0;
for ($i = 0; $i < strlen($str); $i++) {
$hash = $hash * $seed + ord($str[$i]);
}
return $hash;
}
// 添加元素
public function add($str) {
for ($i = 0; $i < $this->hashFuncNum; $i++) {
$hash = $this->_hash($str, $this->powArray[$i]);
$group = $hash % $this->spaceGroupNum;
$pos = $hash % (strlen($this->hashSpaceAssoc[$group]) * 8);
$byteIndex = $pos >> 3;
$bitIndex = $pos & 7;
$this->hashSpaceAssoc[$group][$byteIndex] |= (1 << $bitIndex);
}
}
// 檢查元素
public function check($str) {
for ($i = 0; $i < $this->hashFuncNum; $i++) {
$hash = $this->_hash($str, $this->powArray[$i]);
$group = $hash % $this->spaceGroupNum;
$pos = $hash % (strlen($this->hashSpaceAssoc[$group]) * 8);
$byteIndex = $pos >> 3;
$bitIndex = $pos & 7;
if (!($this->hashSpaceAssoc[$group][$byteIndex] & (1 << $bitIndex))) {
return false; // 確定不存在
}
}
return true; // 可能存在
}
}
SETBIT/GETBIT 或 PHP gmp 擴展,支援分佈式、持久化。n 與目標誤判率 p 計算最優 m、k:m = - (n * ln p) / (ln 2)^2k = (m / n) * ln 2對於極少數誤判為「存在」的關鍵業務(如白名單),可建立小型白名單資料庫二次驗證。
Bloom Filter 以微小的空間換取極快的查詢速度,是大規模系統中不可或缺的「守門員」。PHP 實現雖受限於單進程記憶體,但結合 Redis 等中間件即可構建高性能分佈式過濾服務。