一、概述
1、概念
布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数,它是一种比较巧妙的概率型数据结构,特点是高效地插入和查询。
布隆过滤器用于判断一个元素一定不存在于这个空间,比如黑名单系统。
2、布隆过滤器数据结构
布隆过滤器是一个 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” 这个值存在。
3、布隆过滤器处理流程
第一步:开辟空间
开辟一个长度为m的位数组(或者称二进制向量),这个不同的语言有不同的实现方式,甚至你可以用文件来实现。
第二步:寻找hash函数
获取几个hash函数,前辈们已经发明了很多运行良好的hash函数,比如BKDRHash,JSHash,RSHash等等。这些hash函数我们直接获取就可以了。
第三步:写入数据
将所需要判断的内容经过这些hash函数计算,得到几个值,比如用3个hash函数,得到值分别是1000,2000,3000。之后设置m位数组的第1000,2000,3000位的值位二进制1。
第四步:判断
接下来就可以判断一个新的内容是不是在我们的集合中。判断的流程和写入的流程是一致的。可以对比上面的布隆过滤器数据结构,你可能会有更清晰的认识。
4、如何选择哈希函数个数和布隆过滤器长度
很显然,过小的布隆过滤器很快所有的 bit 位就会都被置为 1,那么查询任何值都会返回“可能存在”,也就起不到过滤的目的了。
布隆过滤器的长度会直接影响误报率,布隆过滤器越长其误报率越小。
另外,哈希函数的个数也需要权衡,个数越多则布隆过滤器 bit 位置为 1 的速度越快,且布隆过滤器的效率越低;但是如果太少的话,那我们的误报率会变高。
5、布隆过滤器的优缺点
优点:
使用更小的空间和更高的效率进行判断。
缺点:
存在一定的误判,并且不能删除元素。
注:想解决Bloom Filter 中不能删除元素的问题,可以使用 Counting Bloom Filter,它是网上提出来的 Bloom Filter 的改进版,Bloom Filter 本身只有0或1,而Bloom Filter 采用的是计数,比如0,4,9 等,删除元素,就将对应的bit位上值减1,这里不做过多介绍,实际生产中,采用这种方案的人也不多。
6、应用场景
(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 个元素