BitMap(二)：布隆過濾器(Bloom Filter)

原理

用一個雜湊演算法(Hash函數)将一個集合元素映射到一個二進制位數組（位數組）中的某一位。如果該位已經被置為1，那麼表示該元素已經存在。為了減少hash沖突問題,是以引用了多個哈希函數,如果通過其中的一個Hash值得出某元素不在集合中，那麼該元素肯定不在集合中。隻有在所有的Hash函數告訴我們該元素在集合中時，才能确定該元素存在于集合中。這便是Bloom-Filter的基本思想。

這是BitMap算法的一個應用，基于BitMap算法但優于BitMap算法。

應用

布隆過濾器的巨大用處就是，能夠迅速判斷一個元素是否在一個集合中。

是以他有如下三個使用場景:

1. 網頁爬蟲對URL的去重，避免爬取相同的URL位址；
2. 反垃圾郵件，從數十億個垃圾郵件清單中判斷某郵箱是否垃圾郵箱（同理，垃圾短信）；
3. 緩存穿透，将所有可能存在的資料緩存放到布隆過濾器中，當黑客通路不存在的緩存時迅速傳回避免緩存及DB挂掉。

優缺點

優點：

• 快速，時間複雜度O(1)
• 節省資源，主要是記憶體資源

缺點：

• 誤判，這是不可避免的，隻能通過多個哈希函數、白名單等手段降低誤判幾率
• 需要另外維護一個集合來存放Key
• 不支援删值操作

舉例

下圖表示有三個hash函數，比如一個集合中有x，y，z三個元素，分别用三個hash函數映射到二進制序列的某些位上，假設我們判斷w是否在集合中，同樣用三個hash函數來映射，結果發現取得的結果不全為1，則表示w不在集合裡面。

PHP + Redis實作

首先定義一個hash函數集合類，這些hash函數不一定都用到，實際上32位hash值的用3個就可以了，具體的數量可以根據你的位序列總量和你需要存入的量決定，上面已經給出最佳值。

/**
 * 布隆過濾器哈希函數，函數僅作參考
 * Class BloomFilterHash
 */
class BloomFilterHash
{
    /**
     * 由Justin Sobel編寫的按位散列函數
     * @param $string string
     * @param $len null
     * @return int
     */
    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 & 0x7FFFFFFF;
    }

    /**
     * 這個哈希函數來自Brian Kernighan和Dennis Ritchie的書“The C Programming Language”。
     * 它是一個簡單的哈希函數，使用一組奇怪的可能種子，它們都構成了31 .... 31 ... 31等模式，它似乎與DJB哈希函數非常相似。
     * @param $string string
     * @param $len null
     * @return int
     */
    public function BKDRHash($string, $len = null)
    {
        $seed = 131; // 31 131 1313 13131 131313 etc..
        $hash = 0;

        $len = strlen($string);
        for($i = 0; $i < $len; $i++)
        {
            $hash = ((floatval($hash * $seed) & 0x7FFFFFFF) + ord($string[$i])) & 0x7FFFFFFF;
        }
        return $hash & 0x7FFFFFFF;
    }

    /**
     * 這是在開源SDBM項目中使用的首選算法。
     * 哈希函數似乎對許多不同的資料集具有良好的總體分布。它似乎适用于資料集中元素的MSB存在高差異的情況。
     * @param $string string
     * @param $len null
     * @return int
     */
    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 & 0x7FFFFFFF;
    }
}
           

接着就是連接配接redis來進行操作

/**
 * 使用redis實作的布隆過濾器
 * Class BloomFilterRedis
 */
abstract class BloomFilterRedis
{
    /**
     * @var 需要使用一個方法來定義bucket的名字
     */
    protected $bucket;

    /**
     * @var array hash函數
     */
    protected $hashFunction;

    /**
     * @var hash 函數對象
     */
    protected $hash;

    /**
     * @var redis 連接配接對象
     */
    protected $redis;

    public function __construct($config = [], $id = 0)
    {
        if (!$this->bucket || !$this->hashFunction) {
            throw new Exception("需要定義bucket和hashFunction", 1);
        }
        $this->hash = new BloomFilterHash();
//        $this->redis = new YourRedis(); //假設這裡你已經連接配接好了
        $this->redis = new Redis();
        $this->redis->connect('127.0.0.1', 6379);
    }

    /**
     * 添加到集合中
     * @param $string string
     * @return mixed
     */
    public function add($string)
    {
        //redis 事務塊的開始
        $pipe = $this->redis->multi();
        foreach ($this->hashFunction as $function) {
            $hash = $this->hash->$function($string);
            $pipe->setBit($this->bucket, $hash, 1);
        }

        //執行redis事務的指令
        return $pipe->exec();
    }

    /**
     * 查詢是否存在, 存在的一定會存在, 不存在有一定幾率會誤判
     * @param $string string
     * @return bool
     */
    public function exists($string)
    {
        //redis 事務塊的開始
        $pipe = $this->redis->multi();
        $len = strlen($string);
        foreach ($this->hashFunction as $function) {
            $hash = $this->hash->$function($string, $len);
            $pipe = $pipe->getBit($this->bucket, $hash);
        }

        //執行redis事務的指令
        $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');
}

//=======================測試===============================

$bloom = new FilteRepeatedComments();
$bloom->add('a');
$bloom->add('b');
$bloom->add('c');
$res1 = $bloom->exists('a');
if($res1){
    echo '字母a存在',"<br>";
}else{
    echo '字母a不存在',"<br>";
}

$res2 = $bloom->exists('d');
if($res2){
    echo '字母d存在',"<br>";
}else{
    echo '字母d不存在',"<br>";
}

//結果
//字母a存在
//字母d不存在
           

參考資料：

http://imhuchao.com/1271.html