php怎么使用布隆过滤器（php怎么使用布隆过滤器代码）

本篇文章给大家谈谈php怎么使用布隆过滤器，以及php怎么使用布隆过滤器代码对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

1、布隆过滤器的基本原理和使用
2、BloomFilter详解（布隆过滤器）
3、布隆过滤器
4、布隆过滤器扩容及删除过期数据
5、布隆过滤器详解

布隆过滤器的基本原理和使用

工作中遇到一个需求，需要从词库中快速判断某个关键字是否存在，词库大小不超过百万，当时脑子第一反应是用hash表相关数据结构，和同事一交流，同事推荐用布隆过滤器，查询效率不输hashmap，而且非常节省存储空间。经过研究发现布隆过滤器挺好用的，这篇文章来说说三点：

1.什么是布隆过滤器。

2.布隆过滤器基本原理。

3.布隆过滤器的使用方式。

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

a.下图是一个初始化后的长度为11的布隆过滤器结构，可以看成一个数组，还未放入任何数据，所有位的值都是0。

b.假如有三个hash函数（hash1、hash2、hash3）此时我们添加一个关键字进去，假设我们添加一个字母"a"，通过三个hash函数分别求出2、5、6，于是把下标为2、5、6的值都改为1。

c.此时我们根据字母"a"去布隆过滤器查找，判断a是否存在的流程如下图，由于对a进行三个hash函数取模得到的2、5、6下标的值都是1，说明这个a大概率已经存在了（为什么是大概率呢？因为布隆过滤器是一种概率型数据结构，存在非常小的误判几率，不能判断某个元素一定百分之百存在，所以只能用在允许有少量误判的场景，不能用在需要100%精确判断存在的场景）。

如果使用字母b进行查找，三个hash函数取模得到的是7、8、9或者3、5、6，发现这些下标对应的值都不全部是1，则判定为不存在。

相对于HashMap的优点：

布隆过滤器节省空间，无需存储全部数据，只需要将多个hash函数取模得到的下标对应位置的值改为1即可，无需存储全部数据，是一种极度节省存储空间的数据结构。

相对于HashMap的缺点：

布隆过滤器无法做到100%精确判断，而HashMap可以。布隆过滤器本质上是赌不同的字符串不太可能所有的哈希函数都发生哈希碰撞，虽然有极低的概率发生，但是基本可以把误判率控制在1%以内。

BloomFilter详解（布隆过滤器）

从上式中可以看出，当m增大或n减小时，都会使得误判率减小，这也符合直觉。

现在计算对于给定的m和n，k为何值时可以使得误判率最低。设误判率为k的函数为：

这说明了若想保持某固定误判率不变，布隆过滤器的bit数m与被add的元素数n应该是线性同步增加的。

三如何设计bloomfilter

此概率为某bit位在插入n个元素后未被置位的概率。因此，想保持错误率低，布隆过滤器的空间使用率需为50%。

bloomfilter的各个参数的错误率

公式推完了，大家可以看看，里面的数学公式基本用到了指数函数对数函数微积分求导法则概率论的知识，大家可以补充看下课本。

个人介绍：杜宝坤，京东联邦学习从0到1构建者，带领团队构建了京东的联邦学习解决方案，实现了电商营销领域支持超大规模的工业化联邦学习解决方案，支持超大规模样本PSI隐私对齐、安全的树模型与神经网络模型等众多模型支持，并且实现了广告侧等业务领域的落地，开创了新的业务增长点，产生了显著的业务经济效益。

个人喜欢研究技术。基于从全链路思考与决策技术规划的考量，研究的领域比较多，从架构、数据到算法与算法框架均有涉及。欢迎喜欢技术的同学和我交流，邮箱： baokun06@163.com

布隆过滤器

最近在做的事情中，有一个小功能点是判断ip是否已经在已有的集合中是否不存在，ip包括ipv4和ipv6两种类型，这种查找的问题，第一反应就是HashMap，但是又想，不合适，为什么那？因为这个集合不是固定的，会随着程序的运行，这个已有的IP集合会越来越大，占内存会很大的，有可能会造成OOM的问题。

如果是仅仅是IPV4的查找，直接按照字符串来存储，如果c语言去写的话一个ip需要用15个字节来保存（“255.255.255.255”），那么如果想的极端些，将所有的IPv4地址都保存的话，几百G的空间是需要的，显然是不合适的。

对于只支持ipv4的场景，可以通过简单的方法来做，可以这样做，就是首先通过转换，将IPV4转成int，比如：

192.168.0.1 这个IP转换如下：

192左移24位： 11000000 00000000 00000000 00000000

168左移16位： 00000000 10101000 00000000 00000000

000左移08位： 00000000 00000000 00000000 00000000

001左移00位： 00000000 00000000 00000000 00000001

按位或结果： 11000000 10101000 00000000 00000001

得到的十进制就是：3232235521L 这个数字，这个数字范围是超过int的，如果用int表示为负数，转成整数后，最大的整数为：4294967295L，如果申请一个很大的数组，计算下，这个数组的内存占用大概是511MB，然后以ip转成的数字作为index，如果这个ip存在则将这一位设置为1，不存在设置为0，这样不仅可以节省内存，还可以做到快速查找，比字符串匹配要快的多,示意图如下：

说明：

如示意图所示，如果192.168.0.1这个ip在集合中存在，则我们可以把数组中的index为：3232235521设置为1。

这种位图的方法，也有比较明显的缺点，就是不好做删除，当然可以改造下结构，添加个计数；在本例中还有个缺点，就是数组太大，范围42亿，虽然可以通过转成int后，再减去最小的ip值作为数组下标，不过数组仍然很大，内存分配上都存在着很大的压力。

鉴于我们多判断ip是否一定不存在这个集合中，可以通过布隆过滤器来实现。

刚才使用位图可以看作用一个映射函数，把ip映射到大数组中，利用的映射函数为f(x)=x。如果x的范围很大，比如我们刚才的ipv4的范围有42亿之多，其实我们在实际使用中远没有用到这么多ip，我们可以对这个映射函数也叫哈希函数来做下改进：f(x) = x%n，这里面的n为我们申请的大数组中所有的位（bit）的个数，这样可以根据我们的内存情况，申请了更小的内存，比如我们可以申请1亿bit的数组，只需要11MB内存，但是这里面有个问题，就是存在着hash冲突的问题。

1和n+1这两个数字，通过f(x) = x%n 映射之后都保存到1这个位置，那么在判断的时候，就会造成误判，本来1是存在的，n+1是不存在的，根据这个映射函数也认为n+1也是存在的了。

为了减轻这种冲突的情况，布隆过滤器采用多个哈希函数，假如我们使用了K个哈希函数，分别对同一个数字求哈希值，那么就会得到K个不同的哈希值，我们分别记作：X1，X2，X3...Xk。我们把这个K个数字作为位图中的下标，将这些下标对应的位图值设置为1。

布隆过滤器有两个特点：

对于我的使用场景来说，只需要判断ip是不是不存在于集合中，如果存在集合中会进一步做准确判断，所以布隆过滤的准确率影响不大，如果要降低错报率，除了多个hash函数外，可以扩大数组从本质上降低误报率。如果想精确了解在特定容量，误报率需要内存的大小，可以通过 ;p=1.0E-7m=k=3 网址看下保存特定容量和误报率，需要的内存大小。

布隆过滤器还可以用于垃圾邮件的发件箱地址过滤，爬虫时候url去重排查等，应该还是相当广泛的。

php怎么使用布隆过滤器（php怎么使用布隆过滤器代码）,php怎么使用布隆过滤器,信息,文章,营销,第1张

布隆过滤器扩容及删除过期数据

我们知道，布隆过滤器是不可变的，但如果布隆过滤器容量确实不够了，该怎么办呢？或者如果要每个月都删除几个月前的去重数据，该如何处理呢？这边要记录一种布隆过滤器的巧用，多个布隆过滤器组成的循环布隆过滤器。

布隆过滤器的细节这边不做赘述，他在创建的时候就确定了容量以及错误率（false postive），为了后续的方便，这边假设我们有了一个可靠的布隆过滤器。

很简单的一个结构，接下去我们会用基础的布隆过滤器去实现最开始说的两个需求。

因为布隆过滤器的不可逆，我们没法重新建一个更大的布隆过滤器然后去把数据重新导入。这边采取的扩容的方法是，保留原有的布隆过滤器，建立一个更大的，新增数据都放在新的布隆过滤器中，去重的时候检查所有的布隆过滤器。

非常巧妙的方法，用一个新的布隆过滤器和多个老的布隆过滤器共同组成一个新的过滤器，提供相同的接口。

为了实现这么一个需求：使用布隆过滤器对url去重，但是每五个月要重新爬取一次。这边介绍一种循环的布隆过滤器，类似于之前的思路，由多个布隆过滤器组成，每个月都清空最早的那个过滤器。demo如下。

一样非常简单的逻辑，只要定期执行 do_circle 即可。

另外，我们可以看到，上边的实现 add 方法只对一个过滤器执行，而 exists 方法对所有过滤器都要执行，比较适用于插入多，但是判断是否重复少的场景。我们还可以换一种方式，应对查询是否重复大于添加操作的场景。

每次的插入操作，我们对所有的过滤器都执行，而查询是否重复，只需要查询最早的过滤器是否存在即可（包含了全部的数据）

布隆过滤器详解

布隆过滤器（英语：Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。

通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为，，。

这个时候，布隆过滤器（Bloom Filter）就应运而生。

了解布隆过滤器原理之前，先回顾下 Hash 函数原理。

哈希函数的概念是：将任意大小的输入数据转换成特定大小的输出数据的函数，转换后的数据称为哈希值或哈希编码，也叫散列值。下面是一幅示意图：

所有散列函数都有如下基本特性：

但是用 hash表存储大数据量时，空间效率还是很低，当只有一个 hash 函数时，还很容易发生哈希碰撞。

BloomFilter 是由一个固定大小的二进制向量或者位图（bitmap）和一系列映射函数组成的。

在初始状态时，对于长度为 m 的位数组，它的所有位都被置为0，如下图所示：

当有变量被加入集合时，通过 K 个映射函数将这个变量映射成位图中的 K 个点，把它们置为 1（假定有两个变量都通过 3 个映射函数）。

查询某个变量的时候我们只要看看这些点是不是都是 1 就可以大概率知道集合中有没有它了

为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。

布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1。

这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。(比如上图中的第 3 位)

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数，另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

布隆过滤器可以表示全集，其它任何数据结构都不能；

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。

另外，一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

在降低误算率方面，有不少工作，使得出现了很多布隆过滤器的变种。

在程序的世界中，布隆过滤器是程序员的一把利器，利用它可以快速地解决项目中一些比较棘手的问题。

如网页 URL 去重、垃圾邮件识别、大集合中重复元素的判断和缓存穿透等问题。

布隆过滤器的典型应用有：

知道了布隆过滤去的原理和使用场景，我们可以自己实现一个简单的布隆过滤器

分布式环境中，布隆过滤器肯定还需要考虑是可以共享的资源，这时候我们会想到 Redis，是的，Redis 也实现了布隆过滤器。

当然我们也可以把布隆过滤器通过 bloomFilter.writeTo() 写入一个文件，放入OSS、S3这类对象存储中。

Redis 提供的 bitMap 可以实现布隆过滤器，但是需要自己设计映射函数和一些细节，这和我们自定义没啥区别。

Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中，给 Redis 提供了强大的布隆去重功能。

在已安装 Redis 的前提下，安装 RedisBloom，有两种方式

直接编译进行安装

使用Docker进行安装