一、概述
1、概念
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数，它是一种比较巧妙的概率型数据结构，特点是高效地插入和查询。
布隆过滤器用于判断一个元素一定不存在于这个空间，比如黑名单系统。
２、布隆过滤器数据结构
布隆过滤器是一个 bit 向量或者说 bit 数组，长这样：
如果我们要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit 位置 1，例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7，则上图转变为：
Ok，我们现在再存一个值 “tencent”，如果哈希函数返回 3、4、8 的话，图继续变为：
值得注意的是，4 这个 bit 位由于两个值的哈希函数都返回了这个 bit 位，因此它被覆盖了。
当我们如果想查询 “dianping” 这个值是否存在，哈希函数返回了 1、5、8三个值，结果我们发现 5 这个 bit 位上的值为 0，说明没有任何一个值映射到这个 bit 位上，因此我们可以很确定地说 “dianping” 这个值不存在。
而当我们需要查询 “baidu” 这个值是否存在的话，那么哈希函数必然会返回 1、4、7，然后我们检查发现这三个 bit 位上的值均为 1，那么我们可以说 “baidu” 存在了么？答案是不可以，只能是 “baidu” 这个值可能存在。
这是为什么呢？答案很简单，因为随着增加的值越来越多，被置为 1 的 bit 位也会越来越多，这样某个值 “taobao” 即使没有被存储过，但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ，那么程序还是会判断 “taobao” 这个值存在。
３、布隆过滤器处理流程
第一步：开辟空间
开辟一个长度为m的位数组（或者称二进制向量），这个不同的语言有不同的实现方式，甚至你可以用文件来实现。
第二步：寻找hash函数
获取几个hash函数，前辈们已经发明了很多运行良好的hash函数，比如BKDRHash，JSHash，RSHash等等。这些hash函数我们直接获取就可以了。
第三步：写入数据
将所需要判断的内容经过这些hash函数计算，得到几个值，比如用3个hash函数，得到值分别是1000，2000，3000。之后设置m位数组的第1000，2000，3000位的值位二进制1。
第四步：判断
接下来就可以判断一个新的内容是不是在我们的集合中。判断的流程和写入的流程是一致的。可以对比上面的布隆过滤器数据结构，你可能会有更清晰的认识。
４、如何选择哈希函数个数和布隆过滤器长度
很显然，过小的布隆过滤器很快所有的 bit 位就会都被置为 1，那么查询任何值都会返回“可能存在”，也就起不到过滤的目的了。
布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。
另外，哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置为 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。
５、布隆过滤器的优缺点
优点：
使用更小的空间和更高的效率进行判断。
缺点：
存在一定的误判，并且不能删除元素。
注：想解决Bloom Filter 中不能删除元素的问题，可以使用 Counting Bloom Filter，它是网上提出来的 Bloom Filter 的改进版，Bloom Filter 本身只有0或1，而Bloom Filter 采用的是计数，比如0，4，9 等，删除元素，就将对应的bit位上值减1，这里不做过多介绍，实际生产中，采用这种方案的人也不多。
６、应用场景
（1）黑名单系统
（2）缓存穿透
二、代码实现
由于Redis实现了setbit和getbit操作，天然适合实现布隆过滤器，redis也有布隆过滤器插件。这里使用php+redis实现布隆过滤器。
1、BloomFilterHash.php (hash函数类)
<?php
declare(strict_types = 1);
/*
* hash函数集合类，用于布隆过滤器使用
*/
class BloomFilterHash
{
/**
* 由Justin Sobel编写的按位散列函数
*
* @param $string
* @param null $len
* @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 % 0xFFFFFFFF) & 0xFFFFFFFF;
}
/**
* 该哈希算法基于AT＆T贝尔实验室的Peter J. Weinberger的工作。
* Aho Sethi和Ulman编写的“编译器（原理，技术和工具）”一书建议使用采用此特定算法中的散列方法的散列函数。
*
* @param $string
* @param null $len
* @return int
*/
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;
$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使用哈希函数。
*
* @param $string
* @param null $len
* @return int
*/
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等模式
*
* @param $string
* @param null $len
* @return int
*/
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存在高差异的情况。
*
* @param $string
* @param null $len
* @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 % 0xFFFFFFFF) & 0xFFFFFFFF;
}
/**
* 由Daniel J. Bernstein教授制作的算法，首先在usenet新闻组comp.lang.c上向世界展示。
* 它是有史以来发布的最有效的哈希函数之一。
*
* @param $string
* @param null $len
* @return int
*/
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章。
*
* @param $string
* @param null $len
* @return int
*/
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/
*
* @param $string
* @param null $len
* @return int
*/
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;
}
}
2、BloomFilterRedis.php （redis 添加、查询元素到/从 布隆过滤器）
<?php
declare(strict_types = 1);
include_once 'BloomFilterHash.php'; // 项目中请用use替代
/**
* 使用redis实现的布隆过滤器
*/
class BloomFilterRedis
{
protected $bucket; // 定义bucket的名字
protected $hashFunction; // 定义使用的hash方法
protected $Hash;
protected $Redis;
/**
* BloomFilterRedis constructor.
* @param string $bucket
* @param array $hashFunction
*/
public function __construct(string $bucket, array $hashFunction)
{
$this->bucket = $bucket;
$this->hashFunction = $hashFunction;
$this->Hash = new BloomFilterHash;
$this->Redis = $this->getRedis();
}
/**
* 添加到集合中
*
* @param $string
* @return array
*/
public function add($string)
{
$pipe = $this->Redis->multi();
foreach ($this->hashFunction as $function) {
$hash = $this->Hash->$function($string);
$pipe->setBit($this->bucket, $hash, true);
}
return $pipe->exec();
}
/**
* 查询是否存在（存在的一定会返回true, 不存在有一定几率返回true，但如果返回false，则说明一定不存在）
*
* @param $string
* @return bool
*/
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();
if (in_array(0, $res)) {
return false;
}
return true;
}
/**
* 设置redis连接
*
* @return Redis
*/
private function getRedis()
{
$redis = new Redis();
$redis->connect('127.0.0.1', 6379);
$redis->auth('haveyb');
$redis->select(8);
return $redis;
}
}
3、index.php (测试文件)
<?php
declare(strict_types = 1);
include_once 'BloomFilterRedis.php'; // 在项目中应该使用use自动加载
// 定义key，并自行从hash函数集中选取几个方法
$object = new BloomFilterRedis('test_bloom', ['JSHash', 'DJBHash', 'ELFHash']);
$object->add('老迟笔记');
$object->add('DockerHub');
// 添加元素到布隆过滤器
var_dump($object->exists('老迟笔记')); // true
echo '<br>';
var_dump($object->exists('DockerHub')); // true
echo '<br>';
var_dump($object->exists('SiNa')); // false
注：使用上面的方法可以存储 2＾32 个元素