php实训布隆过滤器

<?php

/**
 * BitSet 模拟BitSet 在PHP中可以使用Array代替
 */
class BitSet {
    protected $bit = [];

    public function add($index) {
        $this->bit[$index] = 1;
    }

    public function has($index) {
        if(isset($this->bit[$index])) {
            return true;
        }
        return false;
    }
}

/**
 * Hash算法
 */
class HashFunction
{
    protected $size;
    protected $seed;

    public function __construct($size, $seed)
    {
        $this->size = $size;
        $this->seed = $seed;
    }

    public function hash($value)
    {
        $r = 0;
        $l = strlen($value);
        for ($i = 0; $i < $l; $i++) {
            $r = $this->seed * $r + ord($value[$i]);
        }
        return ($this->size - 1) & $r;
    }
}

/**
 * 布隆过滤器
 */
class BloomFilter
{

    /** @var int 一个长度为10 亿的比特位 */
    protected $size = 256 << 22;

    /** @var int[] 为了降低错误率，使用加法hash算法，所以定义一个8个元素的质数数组 */
    protected $seeds = [3, 5, 7, 11, 13, 31, 37, 61];

    /** @var HashFunction[] 相当于构建 8 个不同的hash算法 */
    protected $functions = [];

    /** @var BitSet[] 初始化布隆过滤器的 bitmap */
    protected $bitset = [];

    public function __construct($size = null, $seeds = null)
    {
        if($seeds != null) {
            $this->size = $size;
        }
        if($seeds != null) {
            $this->seeds = $seeds;
        }
        foreach ($this->seeds as $v) {
            $this->functions[$v] = new HashFunction($this->size, $v);
            $this->bitset[$v] = new BitSet();
        }
    }

    /**
     * @param string $str
     */
    public function add($str) {
        if($str != null) {
            foreach ($this->functions as $k => $fun) {
                $this->bitset[$k]->add($fun->hash($str));
            }
        }
    }

    /**
     * @param string $str
     * @return bool
     */
    public function has($str) {
        if($str != null) {
            foreach ($this->functions as $k => $fun) {
                if(!$this->bitset[$k]->has($fun->hash($str))) {
                    return false;
                }
            }
            return true;
        }
        return false;
    }
}


function d($str) {
    if(is_array($str)) {
        echo "[Array]:\n";
        print_r($str);
        echo "\n";
    } else if(is_object($str)) {
        echo "[Object]:\n";
        print_r($str);
        echo "\n";
    } else if(is_bool($str)) {
        echo "[Boolean]: " . ($str ? "true" : "false") . "\n";
    } else {
        echo "[String]: " . $str . "\n";
    }
}

/*
 * 测试函数
 */

d("初始化布隆过滤器");
$f = new BloomFilter;
$l1 = 10000;
$l2 = 10;

d("添加初始数据");
for ($i = 0; $i < $l1; $i ++) {
    $f->add("#" . $i);
//    d("add #{$i}");
}

d("测试判断随机数 {$l2}个");
for ($i = 0; $i < $l2; $i ++) {
//    $s = "#" . rand($l2, $l2 + 1000);
//    $s = "#0";
    $s = "#" . rand(0, $l1 * 2);
    $r = $f->has($s);
    d("判断数字 {$s} >> " . ($r ? "true" : "false"));
}