swoft+Redis实现的布隆过滤器

       布隆过滤器：本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构，特点是高效的插入和查询，可以用来告诉你“某样东西一定不存在或者可能存在”。相比于传统的list，set，map等数据结构，它更高效，占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。

      由于Redis实现了setbit和getbit操作，天然适合实现布隆过滤器，redis也有布隆过滤器插件。这里使用php+redis实现布隆过滤器。

     首先定义一个hash函数集合类，这些hash函数不一定都用到，实际上32位hash值的用3个就可以了，具体的数量可以根据你的位序列总量和你需要存入的量决定，上面已经给出最佳值。

  1 <?php declare(strict_types=1);
  2 namespace App\Common;
  3 
  4 class BloomFilterHash
  5 {
  6     /**
  7      * 由Justin Sobel编写的按位散列函数
  8      */
  9     public function JSHash($string, $len = null)
 10     {
 11         $hash = 1315423911;
 12         $len || $len = strlen($string);
 13         for ($i=0; $i<$len; $i++) {
 14             $hash ^= (($hash << 5) + ord($string[$i]) + ($hash >> 2));
 15         }
 16         return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
 17     }
 18 
 19     /**
 20      * 该哈希算法基于AT＆T贝尔实验室的Peter J. Weinberger的工作。
 21      * Aho Sethi和Ulman编写的“编译器（原理，技术和工具）”一书建议使用采用此特定算法中的散列方法的散列函数。
 22      */
 23     public function PJWHash($string, $len = null)
 24     {
 25         $bitsInUnsignedInt = 4 * 8; //（unsigned int）（sizeof（unsigned int）* 8）;
 26         $threeQuarters = ($bitsInUnsignedInt * 3) / 4;
 27         $oneEighth = $bitsInUnsignedInt / 8;
 28         $highBits = 0xFFFFFFFF << (int) ($bitsInUnsignedInt - $oneEighth);
 29         $hash = 0;
 30         $test = 0;
 31         $len || $len = strlen($string);
 32         for($i=0; $i<$len; $i++) {
 33             $hash = ($hash << (int) ($oneEighth)) + ord($string[$i]); } $test = $hash & $highBits; if ($test != 0) { $hash = (($hash ^ ($test >> (int)($threeQuarters))) & (~$highBits));
 34     }
 35         return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
 36     }
 37 
 38     /**
 39      * 类似于PJW Hash功能，但针对32位处理器进行了调整。它是基于UNIX的系统上的widley使用哈希函数。
 40      */
 41     public function ELFHash($string, $len = null)
 42     {
 43         $hash = 0;
 44         $len || $len = strlen($string);
 45         for ($i=0; $i<$len; $i++) {
 46             $hash = ($hash << 4) + ord($string[$i]); $x = $hash & 0xF0000000; if ($x != 0) { $hash ^= ($x >> 24);
 47             }
 48             $hash &= ~$x;
 49         }
 50         return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
 51     }
 52 
 53     /**
 54      * 这个哈希函数来自Brian Kernighan和Dennis Ritchie的书“The C Programming Language”。
 55      * 它是一个简单的哈希函数，使用一组奇怪的可能种子，它们都构成了31 .... 31 ... 31等模式，它似乎与DJB哈希函数非常相似。
 56      */
 57     public function BKDRHash($string, $len = null)
 58     {
 59         $seed = 131;  # 31 131 1313 13131 131313 etc..
 60         $hash = 0;
 61         $len || $len = strlen($string);
 62         for ($i=0; $i<$len; $i++) {
 63             $hash = (int) (($hash * $seed) + ord($string[$i]));
 64         }
 65         return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
 66     }
 67 
 68     /**
 69      * 这是在开源SDBM项目中使用的首选算法。
 70      * 哈希函数似乎对许多不同的数据集具有良好的总体分布。它似乎适用于数据集中元素的MSB存在高差异的情况。
 71      */
 72     public function SDBMHash($string, $len = null)
 73     {
 74         $hash = 0;
 75         $len || $len = strlen($string);
 76         for ($i=0; $i<$len; $i++) {
 77             $hash = (int) (ord($string[$i]) + ($hash << 6) + ($hash << 16) - $hash);
 78         }
 79         return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
 80     }
 81 
 82     /**
 83      * 由Daniel J. Bernstein教授制作的算法，首先在usenet新闻组comp.lang.c上向世界展示。
 84      * 它是有史以来发布的最有效的哈希函数之一。
 85      */
 86     public function DJBHash($string, $len = null)
 87     {
 88         $hash = 5381;
 89         $len || $len = strlen($string);
 90         for ($i=0; $i<$len; $i++) {
 91             $hash = (int) (($hash << 5) + $hash) + ord($string[$i]);
 92         }
 93         return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
 94     }
 95 
 96     /**
 97      * Donald E. Knuth在“计算机编程艺术第3卷”中提出的算法，主题是排序和搜索第6.4章。
 98      */
 99     public function DEKHash($string, $len = null)
100     {
101         $len || $len = strlen($string);
102         $hash = $len;
103         for ($i=0; $i<$len; $i++) {
104             $hash = (($hash << 5) ^ ($hash >> 27)) ^ ord($string[$i]);
105         }
106         return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
107     }
108 
109     /**
110      * 参考 http://www.isthe.com/chongo/tech/comp/fnv/
111      */
112     public function FNVHash($string, $len = null)
113     {
114         $prime = 16777619; //32位的prime 2^24 + 2^8 + 0x93 = 16777619
115         $hash = 2166136261; //32位的offset
116         $len || $len = strlen($string);
117         for ($i=0; $i<$len; $i++) {
118             $hash = (int) ($hash * $prime) % 0xFFFFFFFF;
119             $hash ^= ord($string[$i]);
120         }
121         return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
122     }
123 }

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

 1 <?php declare(strict_types=1);
 2 namespace App\Common;
 3 
 4 use App\Exception\ApiException;
 5 use Swoft\Redis\Redis;
 6 
 7 abstract class BloomFilterRedis
 8 {
 9     protected $bucket;
10     protected $hashFunction;
11 
12     public function __construct()
13     {
14         if(!$this->bucket || !$this->hashFunction){
15             throw new ApiException('需要定义',400);
16         }
17 
18         $this->Hash = new BloomFilterHash();
19     }
20 
21     public function add($string)
22     {
23         $pipe = Redis::multi();
24         foreach ($this->hashFunction as $function){
25             $hash = $this->Hash->$function($string);
26             $pipe = $pipe->setBit($this->bucket, $hash, true);
27             echo "hash结果：".$hash."\n";
28         }
29 
30         return $pipe->exec();
31     }
32 
33 
34     public function exists($string)
35     {
36         $len = strlen($string);
37         $pipe = Redis::multi();
38         foreach ($this->hashFunction as $function){
39             $hash = $this->Hash->$function($string, $len);
40             $pipe = $pipe->getBit($this->bucket, $hash);
41             echo "hash获取结果：".$hash."\n";
42         }
43 
44         $res = $pipe->exec();
45         foreach ($res as $bit){
46             if(!$bit) return false;
47         }
48         return true;
49     }
50 }

上面定义的是一个抽象类，如果要使用，可以根据具体的业务来使用。比如下面是一个过滤重复内容的过滤器。

 1 <?php declare(strict_types=1);
 2 namespace App\Bean;
 3 
 4 use App\Common\BloomFilterRedis;
 5 use Swoft\Bean\Annotation\Mapping\Bean;
 6 
 7 
 8 /**
 9  * 重复内容过滤器
10  * 该布隆过滤器总位数为2^32位, 判断条数为2^30条. hash函数最优为3个.(能够容忍最多的hash函数个数)
11  * 使用的三个hash函数为
12  * BKDR, SDBM, JSHash
13  * 注意, 在存储的数据量到2^30条时候, 误判率会急剧增加, 因此需要定时判断过滤器中的位为1的的数量是否超过50%, 超过则需要清空.
14  * Class FileRepeatedComments
15  * @package App\Bean
16  * @Bean()
17  */
18 class FileRepeatedComments extends BloomFilterRedis
19 {
20     protected $bucket = 'rptc';
21 
22     protected $hashFunction = array(
23         'BKDRHash', 'SDBMHash', 'JSHash'
24     );
25 }

调用过滤器

 1 <?php
 2 namespace App\Http\Controller;
 3 
 4 use Swoft\Http\Server\Annotation\Mapping\Controller;
 5 use Swoft\Http\Server\Annotation\Mapping\RequestMapping;
 6 use Swoft\Http\Server\Annotation\Mapping\RequestMethod;
 7 use Swoft\Bean\Annotation\Mapping\Inject;
 8 use App\Bean\FileRepeatedComments;
 9 use Swoft\Http\Message\Request;
10 
11 /**
12  * Class TestController
13  * @Controller(prefix="/test")
14  */
15 class TestController
16 {
17     /**
18      * @Inject()
19      * @var FileRepeatedComments
20      */
21     protected $fileRepeatedComments;
22 
23     /**
24      * @RequestMapping(route="setBloomFilter", method={RequestMethod::GET})
25      */
26     public function setBloomFilterRedis(Request $request){
27         $id = $request->get('id');
28         $this->fileRepeatedComments->add($id);
29     }
30 
31 
32     /**
33      * @RequestMapping(route="getBloomFilter", method={RequestMethod::GET})
34      */
35     public function getBloomFilterRedis(Request $request){
36         $id = $request->get('id');
37         if($this->fileRepeatedComments->exists($id)){
38             echo "存在";
39         }else{
40             echo "不存在";
41         }
42     }
43 }

转载地址：https://segmentfault.com/a/1190000038989098