臭大佬

布隆过滤器

它是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

布隆过滤器的优点：

时间复杂度低，增加和查询元素的时间复杂为O(N)，（N为哈希函数的个数，通常情况比较小）
保密性强，布隆过滤器不存储元素本身
存储空间小，如果允许存在一定的误判，布隆过滤器是非常节省空间的

布隆过滤器的缺点：

有一定的误判率，但是可以通过调整参数来降低
无法获取元素本身
很难删除元素

使用场景

如果布隆过滤器判断某个key不存在，则它在数据库中一定不存在，如果判断出某个key存在，可能出现误判。

利用这个判断是否存在的特点可以做很多有趣的事情。

• 解决Redis缓存穿透问题（面试重点）
• 邮件过滤，使用布隆过滤器来做邮件黑名单过滤
• 对爬虫网址进行过滤，爬过的不再爬
• 解决新闻推荐过的不再推荐(类似抖音刷过的往下滑动不再刷到)
• HBase\RocksDB\LevelDB等数据库内置布隆过滤器，用于判断数据是否存在，可以减少数据库的IO请求

布隆过滤器的原理

数据结构

布隆过滤器它实际上是一个很长的二进制向量和一系列随机映射函数。以Redis中的布隆过滤器实现为例，Redis中的布隆过滤器底层是一个大型位数组（二进制数组）+多个无偏hash函数。

一个大型位数组（二进制数组）：

多个无偏hash函数：

无偏hash函数就是能把元素的hash值计算的比较均匀的hash函数，能使得计算后的元素下标比较均匀的映射到位数组中。

如下就是一个简单的布隆过滤器示意图，其中k1、k2代表增加的元素，a、b、c即为无偏hash函数，最下层则为二进制数组。

空间计算

在布隆过滤器增加元素之前，首先需要初始化布隆过滤器的空间，也就是上面说的二进制数组，除此之外还需要计算无偏hash函数的个数。布隆过滤器提供了两个参数，分别是预计加入元素的大小n，运行的错误率f。布隆过滤器中有算法根据这两个参数会计算出二进制数组的大小l，以及无偏hash函数的个数k。

它们之间的关系比较简单：

• 错误率越低，位数组越长，控件占用较大
• 错误率越低，无偏hash函数越多，计算耗时较长

下面是一个免费的在线布隆过滤器在线计算的网址：
布隆过滤器在线网址

增加元素

往布隆过滤器增加元素，添加的key需要根据k个无偏hash函数计算得到多个hash值，然后对数组长度进行取模得到数组下标的位置，然后将对应数组下标的位置的值置为1

• 通过k个无偏hash函数计算得到k个hash值
• 依次取模数组长度，得到数组索引
• 将计算得到的数组索引下标位置数据修改为1

例如，key = Liziba，无偏hash函数的个数k=3，分别为hash1、hash2、hash3。三个hash函数计算后得到三个数组下标值，并将其值修改为1.
如图所示：

查询元素

布隆过滤器最大的用处就在于判断某样东西一定不存在或者可能存在，而这个就是查询元素的结果。其查询元素的过程如下：

• 通过k个无偏hash函数计算得到k个hash值
• 依次取模数组长度，得到数组索引
• 判断索引处的值是否全部为1，如果全部为1则存在（这种存在可能是误判），如果存在一个0则必定不存在

关于误判

哈希（hash）函数有以下特点：

• 如果根据同一个哈希函数得到的哈希值不同，那么这两个哈希值的原始输入值肯定不同。
• 如果根据同一个哈希函数得到的两个哈希值相等，两个哈希值的原始输入值有可能相等，有可能不相等。

由于哈希算法的第二个特点，可能会存在多个元素计算的hash值是相同的，那么它们取模数组长度后的到的数组索引也是相同的，这就是误判的原因。

栗子：

图中有两个key通过hash处理之后值为02，这样就出现了哈希碰撞 ，为了解决这个问题，布隆过滤器引入多个hash函数来降低碰撞的概率。

删除元素

因为在数组上的同一个点有可能有多个输入值映射，如果删除了会影响布隆过滤器里其他元素的判断结果。所以，不能删除布隆过滤器里的元素。

布隆过滤器处理流程

开辟空间

开辟一个长度为m的位数组（或者称二进制向量）。
注意使用时最好不要让实际元素数量远大于初始化数量。

寻找hash函数

获取几个hash函数，前辈们已经发明了很多运行良好的hash函数，比如BKDRHash，JSHash，RSHash等等。这些hash函数我们直接获取就可以了。

写入数据

将所需要判断的内容经过这些hash函数计算，得到几个值，比如用3个hash函数，得到值分别是1000，2000，3000。之后设置m位数组的第1000，2000，3000位的值位二进制1。

判断

接下来就可以判断一个新的内容是不是在我们的集合中。判断的流程和写入的流程是一致的。

Redis 集成布隆过滤器

下载地址：https://github.com/RedisBloom/RedisBloom/releases

安装&编译

下载

选择 自己要的版本：https://github.com/RedisBloom/RedisBloom/releases

wget https://github.com/RedisBloom/RedisBloom/archive/refs/tags/v2.2.14.tar.gz

解压

tar -zxvf v2.2.14.tar.gz

编译

cd RedisBloom-2.2.14/
make

查看编译结果

复制到redis目录

为了便于管理，把编译好的文件放到redis安装目录下：

// 假设已经在 redis安装目录下

cp /root/RedisBloom-2.2.14/redisbloom.so redisbloom.so

Redis集成

在redis.conf配置文件中加入RedisBloom的redisbloom.so文件的地址

loadmodule /www/server/redis/redisbloom.so

重启才生效！

集成验证

进入 redis 命令行

redis-cli

如果有设置密码

auth "你的redis密码"

判断是否存在 choudalao

bf.exists user choudalao

有结果出来了，说明集成是OK的。

php-redis 布隆过滤器

BloomController

<?php
/**
 * Description:
 * User: Vijay <1937832819@qq.com>
 * Site: https://www.choudalao.com/
 * Date: 2022/5/14
 * Time: 1:02
 */

namespace App\Http\Controllers\Api;

use App\Libs\BloomFilter;
use Predis\Client;
use App\Http\Controllers\Controller;

class BloomController extends Controller
{
    protected $redis = null;

    public function __construct()
    {
        // 这是laravel的redis连接方式，根据自己框架修改就行
        $config = config('database.redis.default');
        $this->redis = new Client($config);
        $this->redis->auth(env('REDIS_PASSWORD'));
    }

    /**
     * 向布隆过滤器压入字符串
     * 这里使用了两个hash函数
     *
     * @return false|string
     */
    public function put()
    {
        $redis = $this->redis;
        $HashFunctionArr = ['JSHash', 'PJWHash'];
        $RedisKey = 'test';
        $BloomLength = 8;//设置布隆位阵列的长度，hash后的数值对其取余
        $BloomFilter = new BloomFilter($redis, $HashFunctionArr, $RedisKey, $BloomLength);
        $res = $BloomFilter->put('joker');
        return json_encode($res);
    }

    /**
     * 判断是否存在
     *
     * @return false|string
     */
    public function exists()
    {
        $redis = $this->redis;
        $HashFunctionArr = ['JSHash', 'PJWHash'];
        $RedisKey = 'test';
        $BloomLength = 8;//设置布隆位阵列的长度，hash后的数值对其取余
        $BloomFilter = new BloomFilter($redis, $HashFunctionArr, $RedisKey,$BloomLength);
        $res = $BloomFilter->isExists('joker');

        return json_encode($res);
    }


}

BloomFilter

<?php
/**
 * Description:
 * User: Vijay <1937832819@qq.com>
 * Site: https://www.choudalao.com/
 * Date: 2022/5/14
 * Time: 1:15
 */

namespace App\Libs;

use Predis\Client as Redis;

class BloomFilter
{
    // hash 函数数组
    public $HashFunctionArr;
    public $Redis;
    public $RedisKey;
    public $BloomLength;

    public function __construct(Redis $redis, Array $HashFunctionArr, string $RedisKey, int $BloomLength = 0)
    {
        $this->HashFunctionArr = $HashFunctionArr;
        $this->Redis = $redis;
        $this->RedisKey = $RedisKey;
        $this->BloomLength = $BloomLength;
    }

    /**
     * 添加 : 将哈希函数计算后的数字，在二进制对应位置置为1
     * 返回 : hash处理后的数字
     *
     * @param string $string
     * @return mixed
     */
    public function put(string $string)
    {
        $arr = [];
        foreach ($this->HashFunctionArr as $function) {
            $arr[] = $hash = $this->BloomLength == 0 ?
                BloomFilterHash::$function($string) :
                BloomFilterHash::$function($string) % $this->BloomLength;
            $this->Redis->setBit($this->RedisKey, $hash, 1);
        }

        return $arr;

    }

    /**
     * 查询是否存在
     *  1,存在的一定会存在
     *  2,不存在有一定几率会误判
     *
     * @param string $string
     * @return bool
     */
    public function isExists(string $string)
    {
        $len = strlen($string);
        $res = [];
        foreach ($this->HashFunctionArr as $function) {
            $hash = $this->BloomLength == 0 ?
                BloomFilterHash::$function($string, $len) :
                BloomFilterHash::$function($string, $len) % $this->BloomLength;
            $res[] = $this->Redis->getBit($this->RedisKey, $hash);
        }
        foreach ($res as $bit) {
            if ($bit == 0) {
                return false;
            }
        }
        return true;
    }
}

BloomFilterHash

<?php
/**
 * Description:
 * User: Vijay <1937832819@qq.com>
 * Site: https://www.choudalao.com/
 * Date: 2022/5/14
 * Time: 1:20
 */

namespace App\Libs;


class BloomFilterHash
{
    /**
     * 由Justin Sobel编写的按位散列函数
     */
    public static 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 static 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 static 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 static 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 static 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 static 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 static 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 static 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;
    }
}

本文参考：
https://blog.csdn.net/qq_41125219/article/details/119982158
https://www.freesion.com/article/35951350402/