引言
在介绍布隆过滤器之前，我们首先介绍了几个场景。
场景一
在高并发计数系统中，如果是key没有计数，此时我们应该返回0，但访问key不存在，相当于每次访问缓存都不起作用。因此，如何避免频繁访问0key缓存被击穿？
有人说， 将这个key值是0存储缓存吗？的确，这是一个很好的计划。在大多数情况下，我们都这样做，当访问一个不存在的key设置过期标志，然后放入缓存。然而，这样做的缺点也很明显，浪费内存，无法抵抗随机性key攻击。
场景二
在黑名单系统中，我们需要设置很多黑名单内容。例如，在判断垃圾邮件时，我们需要设置一个黑名单用户。例如，爬虫系统，我们应该记录已访问的链接，以避免下次访问的重复链接。
在邮件少或用户少的情况下，我们可以用普通数据库自带的查询来完成。当数据量过大时，为了保证速度，我们通常会将结果缓存到内存中，并使用数据结构hash表。这种搜索速度是O(1)，但内存消耗也惊人。例如，如果我们需要存储10亿个数据，平均每个数据占据32个字节，则需要64个内存G，这已经是一个惊人的大小了。
一种解决方案
能不能有个想法吗？查询速度是O(1)消耗内存特别小？前辈门早就想出了一个很好的解决方案。因为上面提到的场景判断结果只有两种状态(或不，存在或不存在)，所以存储的数据可以用位来表示！数据本身可以通过一个hash计算一个函数key，这个key这是一个位置key对值为0或1(因为只有两种状态)，如下图所示:
布隆过滤器原理
以上思路其实是布隆过滤器的思路，只是因为hash多于函数的限制，多个字符串很可能hash一个值。为了解决这个问题，布隆过滤器引入了多个值。hash降低误判率的函数。
下图显示三个hash例如，集合中有函数x，y，z三个元素分别使用三个元素hash函数映射到二进制序列的某些位置，假设我们判断w是否集合，也使用三个hash函数映射，结果发现结果不全为1，说明w不在集合中。
布隆过滤器处理工艺
布隆过滤器应用很广泛，比如垃圾邮件过滤，爬虫的url过滤，防止缓存击穿等。以下是布隆过滤器的完整过程，我相信读者应该能够理解布隆过滤器是如何工作的。
第一步:开放空间
打开一个长度为m的位数组(或二进制向量)，这种语言有不同的实现方式，甚至可以用文件来实现。
第二步：寻找hash函数
获取几个hash函数，前辈们已经发明了很多运行良好的hash函数，比如BKDRHash，JSHash，RSHash等等。这些hash我们可以直接获取函数。
第三步：写入数据
通过这些内容需要判断。hash计算函数，得到几个值，比如三个hash函数，得到值分别为1000、2000、3000。然后设置m位数组的第1000、2000、3000值二进制1。
第四步：判断
接下来，我们可以判断新内容是否在我们的集合中。判断过程与写入过程一致。
误判问题
虽然布隆过滤器非常高效(写入和判断都是O（1）所需的存储空间很小)，但缺点也很明显，就是会误判。当集合中的元素越来越多，二进制序列中1的数量越来越多时，很容易误判一个字符串是否在集合中，原本不在集合中的字符串会被判断在集合中。
数学推导
布隆过滤器的原理很简单，但是hash如何判断函数个数，误判率是多少？
假设二进制序列有m位，当字符串通过时hash到某一位的概率如下：
1m
也就是说，当前位置被逆转为1的概率：
p(1)=1m
那么这个人没有被逆转的概率是:
p(0)=1?1m
假设我们存储n个元素，使用khash函数，此时没有被翻转的概率为：
p(0)=(1?1m)nk
在什么情况下，我们会误判，也就是说，不应该被翻转的位置被翻转，结果被翻转，也就是说，
p(误判)=1?(1?1m)nk
因为只有k个hash函数同时误判，整体误判，最终误判的概率是
p(误判)=(1?(1?1m)nk)k
要使得误判率最低，那么我们需要求误判与m、n、k现在假设m和n固定，我们计算一下k。可以先看看这个公式：
(1?1m)nk
因为我们的m很大，我们通常使用2^32作为m值。上面的公式有一个重要的极限
limx→∞(1 1x)x=e
因此，误判率的公式可以写成
p(误判)=(1?(e)?nk/m)k
接下来令t=?n/m，双方同时取对数，求导，得到：
p′1p=ln(1?etk) klnet(?etk)1?etk
让p′=0，等式后面的0，最后的结果是
(1?etk)ln(1?etk)=etklnetk
计算出的k为ln2mn，约等于0.693mn，将k代入p(误判)我们可以得到概率和m、n关系，最终结果
(1/2)ln2mn，约等于0.6185m/n
以上我们得出了最好的hash函数个数、误判率和mn之前的关系。
下表是m与n比值在k个hash函数下面的误判率
m/nkk=1k=2k=3k=4k=5k=6k=7k=8
21.390.3930.400
32.080.2830.2370.253
42.770.2210.1550.1470.160
53.460.1810.1090.0920.0920.101
64.160.1540.08040.06090.05610.05780.0638
74.850.1330.06180.04230.03590.03470.0364
85.550.1180.04890.03060.0240.02170.02160.0229
96.240.1050.03970.02280.01660.01410.01330.01350.0145
106.930.09520.03290.01740.01180.009430.008440.008190.00846
117.620.08690.02760.01360.008640.00650.005520.005130.00509
128.320.080.02360.01080.006460.004590.003710.003290.00314
139.010.0740.02030.008750.004920.003320.002550.002170.00199
149.70.06890.01770.007180.003810.002440.001790.001460.00129
1510.40.06450.01560.005960.0030.001830.001280.0010.000852
1611.10.06060.01380.0050.002390.001390.0009350.0007020.000574
1711.80.05710.01230.004230.001930.001070.0006920.0004990.000394
1812.50.0540.01110.003620.001580.0008390.0005190.000360.000275
1913.20.05130.009980.003120.00130.000663&nsp;0.000394 0.000264 0.000194
20 13.9 0.0488 0.00906 0.0027 0.00108 0.00053 0.000303 0.000196 0.00014
21 14.6 0.0465 0.00825 0.00236 0.000905 0.000427 0.000236 0.000147 0.000101
22 15.2 0.0444 0.00755 0.00207 0.000764 0.000347 0.000185 0.000112 7.46e-05
23 15.9 0.0425 0.00694 0.00183 0.000649 0.000285 0.000147 8.56e-05 5.55e-05
24 16.6 0.0408 0.00639 0.00162 0.000555 0.000235 0.000117 6.63e-05 4.17e-05
25 17.3 0.0392 0.00591 0.00145 0.000478 0.000196 9.44e-05 5.18e-05 3.16e-05
26 18 0.0377 0.00548 0.00129 0.000413 0.000164 7.66e-05 4.08e-05 2.42e-05
27 18.7 0.0364 0.0051 0.00116 0.000359 0.000138 6.26e-05 3.24e-05 1.87e-05
28 19.4 0.0351 0.00475 0.00105 0.000314 0.000117 5.15e-05 2.59e-05 1.46e-05
29 20.1 0.0339 0.00444 0.000949 0.000276 9.96e-05 4.26e-05 2.09e-05 1.14e-05
30 20.8 0.0328 0.00416 0.000862 0.000243 8.53e-05 3.55e-05 1.69e-05 9.01e-06
31 21.5 0.0317 0.0039 0.000785 0.000215 7.33e-05 2.97e-05 1.38e-05 7.16e-06
32 22.2 0.0308 0.00367 0.000717 0.000191 6.33e-05 2.5e-05 1.13e-05 5.73e-06
php+Redis实现的布隆过滤器
由于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
$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
$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
$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
$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
$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
$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
$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
$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();
}
/**
* 查询是否存在, 存在的一定会存在, 不存在有一定几率会误判
*/
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');
}
总结
以上所述是小编给大家介绍的布隆过滤器(bloom filter)及php和redis实现布隆过滤器的方法，希望对大家有所帮助！