关于php:phpRedis实现的布隆过滤器

因为 Redis 实现了 setbit 和 getbit 操作，人造适宜实现布隆过滤器，redis 也有布隆过滤器插件。这里应用 php+redis 实现布隆过滤器。

首先定义一个 hash 函数汇合类，这些 hash 函数不肯定都用到，实际上 32 位 hash 值的用 3 个就能够了，具体的数量能够依据你的位序列总量和你须要存入的量决定，下面曾经给出最佳值。

class BloomFilterHash
{
    /**
     * 由 Justin Sobel 编写的按位散列函数
     */
    public function JSHash($string, $len = null)
    {
        $hash = 1315423911;
        $len || $len = strlen($string);
        for ($i=0; $i<$len; $i++) {$hash ^= (($hash << 5) + ord($string[$i]) + ($hash >> 2));
        }
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 该哈希算法基于 AT&T 贝尔实验室的 Peter J. Weinberger 的工作。* Aho Sethi 和 Ulman 编写的“编译器（原理，技术和工具）”一书倡议应用采纳此特定算法中的散列办法的散列函数。*/
    public function PJWHash($string, $len = null)
    {
        $bitsInUnsignedInt = 4 * 8; //（unsigned int）（sizeof（unsigned int）* 8）;
        $threeQuarters = ($bitsInUnsignedInt * 3) / 4;
        $oneEighth = $bitsInUnsignedInt / 8;
        $highBits = 0xFFFFFFFF << (int) ($bitsInUnsignedInt - $oneEighth);
        $hash = 0;
        $test = 0;
        $len || $len = strlen($string);
        for($i=0; $i<$len; $i++) {$hash = ($hash << (int) ($oneEighth)) + ord($string[$i]); } $test = $hash & $highBits; if ($test != 0) {$hash = (($hash ^ ($test >> (int)($threeQuarters))) & (~$highBits));
        }
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 相似于 PJW Hash 性能，但针对 32 位处理器进行了调整。它是基于 UNIX 的零碎上的 widley 应用哈希函数。*/
    public function ELFHash($string, $len = null)
    {
        $hash = 0;
        $len || $len = strlen($string);
        for ($i=0; $i<$len; $i++) {$hash = ($hash << 4) + ord($string[$i]); $x = $hash & 0xF0000000; if ($x != 0) {$hash ^= ($x >> 24);
            }
            $hash &= ~$x;
        }
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 这个哈希函数来自 Brian Kernighan 和 Dennis Ritchie 的书“The C Programming Language”。* 它是一个简略的哈希函数，应用一组奇怪的可能种子，它们都形成了 31 .... 31 ... 31 等模式，它仿佛与 DJB 哈希函数十分类似。*/
    public function BKDRHash($string, $len = null)
    {
        $seed = 131;  # 31 131 1313 13131 131313 etc..
        $hash = 0;
        $len || $len = strlen($string);
        for ($i=0; $i<$len; $i++) {$hash = (int) (($hash * $seed) + ord($string[$i]));
        }
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 这是在开源 SDBM 我的项目中应用的首选算法。* 哈希函数仿佛对许多不同的数据集具备良好的总体散布。它仿佛实用于数据集中元素的 MSB 存在高差别的状况。*/
    public function SDBMHash($string, $len = null)
    {
        $hash = 0;
        $len || $len = strlen($string);
        for ($i=0; $i<$len; $i++) {$hash = (int) (ord($string[$i]) + ($hash << 6) + ($hash << 16) - $hash);
        }
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 由 Daniel J. Bernstein 传授制作的算法，首先在 usenet 新闻组 comp.lang.c 上向世界展现。* 它是有史以来公布的最无效的哈希函数之一。*/
    public function DJBHash($string, $len = null)
    {
        $hash = 5381;
        $len || $len = strlen($string);
        for ($i=0; $i<$len; $i++) {$hash = (int) (($hash << 5) + $hash) + ord($string[$i]);
        }
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * Donald E. Knuth 在“计算机编程艺术第 3 卷”中提出的算法，主题是排序和搜寻第 6.4 章。*/
    public function DEKHash($string, $len = null)
    {$len || $len = strlen($string);
        $hash = $len;
        for ($i=0; $i<$len; $i++) {$hash = (($hash << 5) ^ ($hash >> 27)) ^ ord($string[$i]);
        }
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }

    /**
     * 参考 http://www.isthe.com/chongo/tech/comp/fnv/
     */
    public function FNVHash($string, $len = null)
    {
        $prime = 16777619; //32 位的 prime 2^24 + 2^8 + 0x93 = 16777619
        $hash = 2166136261; //32 位的 offset
        $len || $len = strlen($string);
        for ($i=0; $i<$len; $i++) {$hash = (int) ($hash * $prime) % 0xFFFFFFFF;
            $hash ^= ord($string[$i]);
        }
        return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
    }
}

接着就是连贯 redis 来进行操作

/**
 * 应用 redis 实现的布隆过滤器
 */
abstract class BloomFilterRedis
{
    /**
     * 须要应用一个办法来定义 bucket 的名字
     */
    protected $bucket;

    protected $hashFunction;

    public function __construct($config, $id)
    {if (!$this->bucket || !$this->hashFunction) {throw new Exception("须要定义 bucket 和 hashFunction", 1);
        }
        $this->Hash = new BloomFilterHash;
        $this->Redis = new YourRedis; // 假如这里你曾经连贯好了
    }

    /**
     * 增加到汇合中
     */
    public function add($string)
    {$pipe = $this->Redis->multi();
        foreach ($this->hashFunction as $function) {$hash = $this->Hash->$function($string);
            $pipe->setBit($this->bucket, $hash, 1);
        }
        return $pipe->exec();}

    /**
     * 查问是否存在, 如果已经写入过，必然回 true，如果没写入过，有肯定几率会误判为存在
     */
    public function exists($string)
    {$pipe = $this->Redis->multi();
        $len = strlen($string);
        foreach ($this->hashFunction as $function) {$hash = $this->Hash->$function($string, $len);
            $pipe = $pipe->getBit($this->bucket, $hash);
        }
        $res = $pipe->exec();
        foreach ($res as $bit) {if ($bit == 0) {return false;}
        }
        return true;
    }

}

下面定义的是一个抽象类，如果要应用，能够依据具体的业务来应用。比方上面是一个过滤反复内容的过滤器。

/**
 * 反复内容过滤器
 * 该布隆过滤器总位数为 2^32 位, 判断条数为 2^30 条. hash 函数最优为 3 个.(可能容忍最多的 hash 函数个数)
 * 应用的三个 hash 函数为
 * BKDR, SDBM, JSHash
 *
 * 留神, 在存储的数据量到 2^30 条时候, 误判率会急剧减少, 因而须要定时判断过滤器中的位为 1 的的数量是否超过 50%, 超过则须要清空.
 */
class FilteRepeatedComments extends BloomFilterRedis
{
    /**
     * 示意判断反复内容的过滤器
     * @var string
     */
    protected $bucket = 'rptc';

    protected $hashFunction = array('BKDRHash', 'SDBMHash', 'JSHash');
}