PHP实现布隆过滤器

说明

  • 代码仅供参考实现方式
  • 实际过程中 PHP 如果需要用到布隆过滤器还是得依赖于 Redis 布隆过滤器扩展
  • 毕竟PHP并非常驻内存的应用程序,存储在 BitSet表 里面的数据当进程结束后会丢失

代码实现

<?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"));
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
本帖由系统于 4个月前 自动加精
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
讨论数量: 12
fatrbaby

我用redis存储实现过:github.com/xiaker/bloom-filter

4个月前 评论

加点料.. 不然seed好像起反作用

//  HashFunction
public $seed;
// BloomFilter  constructor
 foreach ($this->seeds as $v) {
      $this->functions[] = new HashFunction($this->size, $v);
     $this->bitset[$v] = new BitSet();
}


//add
public function add($str) {
    if($str != null) {
        foreach ($this->functions as $fun) {
//                d($fun->hash($str));
            $this->bitset[$fun->seed]->add($fun->hash($str));
        }
    }
}

//has
public function has($str) {
    if($str != null) {
        foreach ($this->functions as $fun) {
            if(!$this->bitset[$fun->seed]->has($fun->hash($str))) {
                return false;
            }
        }
        return true;
    }
    return false;
}
4个月前 评论
h6play (楼主) 4个月前
Hesunfly

mark

4个月前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!