PHP + Redis 实现布隆过滤器

什么是布隆过滤器?

布隆过滤器是一种空间效率很高的随机数据结构，专门用来检测集合中是否存在特定的元素。布隆过滤器由一个长度为m比特的位数组与k个独立的哈希函数组成的数据结构。位数组初始化均为0，所有的哈希函数都可以分别把输入数据尽量均匀地散列。当要向布隆过滤器中插入一个元素时，该元素经过k个哈希函数计算产生k个哈希值，以哈希值作为位数组中的下标，将所有k个对应的比特值由0置为1。当要查询一个元素时，同样将其经过哈希函数计算产生哈希值，然后检查对应的k个比特值：如果有任意一个比特为0，表明该元素一定不在集合中；如果所有比特均为1，表明该元素有可能性在集合中

由于可能出现哈希碰撞，不同元素计算的哈希值有可能一样，导致一个不存在的元素有可能对应的比特位为1，这就是所谓“假阳性”（false positive）。相对地，“假阴性”（false negative）在BF中是绝不会出现的。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省

所以，布隆过滤器认为不在的，一定不会在集合中；布隆过滤器认为在的，不一定存在集合中

算法

1.选取k个哈希函数，记为 {h1,h2,…,hk}
2.假设现在有n个元素需要被映射到bit数组中，bit数组的长度是m。初始时，将m位的bit数组的每个位置的元素都置为0
3.现在，把这个n个元素依次用第1步选取的k个哈希函数映射到bit数组的位置上，bit数组被映射到的位置的元素变为1。显然，一个元素能被映射到k个位置上。过程如图所示，现在把元素集合{x,y,z}通过3个哈希函数映射到一个二进制数组中
4.最后，需要检查一个元素是否在已有的集合中时，同样用这k个哈希函数把要判断的元素映射到bit数组的位置上，只要bit数组被映射到的位中有一个位不是1，那一定说明了这个元素不在已有的集合内。如图所示，检查w是否在集合中时，有一个哈希函数将ww映射到了bit数组的元素为0的位置

PHP + Redis 实现

<?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"));
}