您现在的位置：程式碼之家 >> 編程語言 > >> 網頁程式設計 >> PHP 程式設計 >> PHP 綜合知識

PHP 實現布隆過濾器：海量數據去重與存在性判斷的高效算法

編輯：PHP 綜合知識

原理介紹

布隆過濾器由位數組與多個哈希函數組成。添加元素時，經各哈希函數映射到位數組的多個位置置 1；查詢時，若所有對應位均為 1 則「可能存在」，若有任一為 0 則「一定不存在」。犧牲微小誤判率（假陽性），換取極高空間效率與 O(k) 時間複雜度。

簡單版演示

$set = [1,2,3,4,5,6];
$bloom = array_fill(0, 10, 0);
foreach ($set as $k) $bloom[$k] = 1;
var_dump($bloom); // [1,1,1,1,1,1,0,0,0,0]
echo $bloom[9] ? '在 set 中' : '不在 set 中'; // 不在

生產級類實現

class bloom_filter {
    private $hash_func_num, $space_group_num, $hash_space_assoc = [], $pow_array, $chr_array, $ord_array, $hash_func_pos;
    private $write_num = 0, $ext_num = 0, $one_num = 8;

    function __construct($hash_func_num = 1, $space_group_num = 1) {
        $max_length = pow(2, 25); // 32MB per group
        $binary = pack('C', 0);
        for ($i=0; $i<$space_group_num; $i++) $this->hash_space_assoc[$i] = str_repeat($binary, $max_length);
        $this->pow_array = [0=>1,1=>2,2=>4,3=>8,4=>16,5=>32,6=>64,7=>128];
        for ($i=0; $i<256; $i++) { $chr=chr($i); $this->chr_array[$i]=$chr; $this->ord_array[$chr]=$i; }
        $this->hash_func_pos = [0=>[0,7,1],1=>[7,7,1],2=>[14,7,1],3=>[21,7,1],4=>[28,7,1],5=>[33,7,1],6=>[17,7,1]];
        $this->hash_func_num = $hash_func_num ?: count($this->hash_func_pos);
        $this->space_group_num = $space_group_num;
    }

    function add($key) {
        $hash_bit_set = 0;
        $hash_basic = sha1($key);
        $hash_space = hexdec(substr($hash_basic,0,4)) % $this->space_group_num;
        for ($i=0; $i<$this->hash_func_num; $i++) {
            $hash = hexdec(substr($hash_basic, $this->hash_func_pos[$i][0], $this->hash_func_pos[$i][1]));
            $bit_pos = $hash >> 3;
            $max = $this->ord_array[$this->hash_space_assoc[$hash_space][$bit_pos]];
            $num = $hash - $bit_pos * $this->one_num;
            $bit_val = ($max >> $num) & 0x01;
            if (!$bit_val) {
                $max |= $this->pow_array[$num];
                $this->hash_space_assoc[$hash_space][$bit_pos] = $this->chr_array[$max];
                $this->write_num++;
            } else $hash_bit_set++;
        }
        if ($hash_bit_set == $this->hash_func_num) { $this->ext_num++; return true; }
        return false;
    }

    function get_stat() { return ['ext_num'=>$this->ext_num, 'write_num'=>$this->write_num]; }
}

// 測試
$bf = new bloom_filter(6, 1); // 6 hash, 1 group (32MB)
$list = ['https://test/1','https://test/2','https://test/3','https://test/4','https://test/5','https://test/6','https://test/1','https://test/2'];
foreach ($list as $v) if ($bf->add($v)) echo $v, "\n"; // 僅輸出重複項
print_r($bf->get_stat());