引言
在介绍布隆过滤器之前我们首先引入几个场景。
场景一
在一个高并发的计数系统中，如果一个key没有计数，此时我们应该返回0，但是访问的key不存在，相当于每次访问缓存都不起作用了。那么如何避免频繁访问数量为0的key而导致的缓存被击穿？
有人说， 将这个key的值置为0存入缓存不就行了吗？确实，这是一个好的方案。大部分情况我们都是这样做的，当访问一个不存在的key的时候，设置一个带有过期时间的标志，然后放入缓存。不过这样做的缺点也很明显，浪费内存和无法抵御随机key攻击。
场景二
在一个黑名单系统中，我们需要设置很多黑名单内容。比如一个邮件系统，我们需要设置黑名单用户，当判断垃圾邮件的时候，要怎么去做。比如爬虫系统，我们要记录下来已经访问过的链接避免下次访问重复的链接。
在邮件很少或者用户很少的情况下，我们用普通数据库自带的查询就能完成。在数据量太多的时候，为了保证速度，通常情况下我们会将结果缓存到内存中，数据结构用hash表。这种查找的速度是O(1)，但是内存消耗也是惊人的。打个比方，假如我们要存10亿条数据，每条数据平均占据32个字节，那么需要的内存是64G，这已经是一个惊人的大小了。
一种解决思路
能不能有一种思路，查询的速度是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函数计算，得到几个值，比如用3个hash函数，得到值分别是1000，2000，3000。之后设置m位数组的第1000，2000，3000位的值位二进制1。
第四步：判断
接下来就可以判断一个新的内容是不是在我们的集合中。判断的流程和写入的流程是一致的。
误判问题
布隆过滤器虽然很高效（写入和判断都是O(1)，所需要的存储空间极小），但是缺点也非常明显，那就是会误判。当集合中的元素越来越多，二进制序列中的1的个数越来越多的时候，判断一个字符串是否在集合中就很容易误判，原本不在集合里面的字符串会被判断在集合里面。
数学推导
布隆过滤器原理十分简单，但是hash函数个数怎么去判断，误判率有多少？
假设二进制序列有m位，那么经过当一个字符串hash到某一位的概率为：
1m
也就是说当前位被反转为1的概率：
p(1)=1m
那么这一位没有被反转的概率为：
p(0)=1"color: #ff0000">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<$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();
}
/**
* 查询是否存在, 存在的一定会存在, 不存在有一定几率会误判
*/
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实现布隆过滤器的方法，希望对大家有所帮助！