布隆过滤器
它是一种独特的数据结构，用以判断：一个数据可能存在或一定不存在
算法思路：
- 开一个指定长度的数组，将所有的元素值设为0
- 添加元素时，执行hash，得到多个位置下标，将数组对应位置设置为1
- 检查元素是否存在时，执行hash，得到多个位置下标，查看数组中对应下标的值： 1> 如果值均为1，则可能存在 2> 如果值有一个是0，则一定不存在
综上所述，布隆过滤器可以用来判断一定不存在的值，且效率较高，但是随着插入的数据不断增加，判断错误的概率也逐渐变大。有一个极端情况就是全部位置都为1，这个时候就什么都判断不出来了。
示例代码
主要使用
pybloom_live
github项目主页：https://github.com/joseph-fox/python-bloomfilter
一般有两种使用方法：
- 一种是固定容量限制的布隆过滤器，当加入的元素大于容量限制时会报错，这样会保证错误率小于给定的概率
from pybloom_live import BloomFilterbf = BloomFilter(1000)# 固定最大容量1000bf.add("a")print("a"in bf)# Trueprint("b"in bf)# False - 另一种是可伸缩的过滤器，当加入的元素大于容量限制时不会报错，但会增加错误率
from pybloom_live import ScalableBloomFilterscala_bf = ScalableBloomFilter(1000)scala_bf.add("a")print("a"in scala_bf)# Trueprint("b"in scala_bf)# False
参考文章
python-布隆过滤器：https://www.cnblogs.com/yscl/p/12003359.html
标签：
python
本文转载自: https://blog.csdn.net/weixin_35757704/article/details/122276877
版权归原作者 呆萌的代Ma 所有， 如有侵权，请联系我们删除。
版权归原作者 呆萌的代Ma 所有， 如有侵权，请联系我们删除。