python BloomFilter(布隆过滤器)

简单解释下。

bloomfilter：是一个通过多哈希函数映射到一张表的数据结构，能够快速的判断一个元素在一个集合内是否存在，具有很好的空间和时间效率。（典型例子，爬虫url去重）

原理：

BloomFilter 会开辟一个m位的bitArray(位数组)，开始所有数据全部置 0 。当一个元素过来时，能过多个哈希函数（h1,h2,h3....）计算不同的在哈希值，并通过哈希值找到对应的bitArray下标处，将里面的值 0 置为 1 。

关于多个哈希函数，它们计算出来的值必须 [0,m) 之中。

 

例子：

有这么一个字符串 “12345”

假设长度为 10 的bitArray，通过 5 个哈希函数求值。如下图：

另外说明一下，当来查找对应的值时，同样通过哈希函数求值，再去寻找数组的下标，如果所有下标都为1时，元素存在。当然也存在错误率。（如：当数组全部为1时，那么查找什么都是存在的），但是这个错误率的大小，取决于数组的位数和哈希函数的个数。

 

安装库（windows下）

python中同样实现了。bloomFilter库。

python2安装：pip install pybloom

python3安装：pip install pybloom-live 

这里说明一下，python3安装时，要安装live版本。pybloom版本在python3中不支持。

同时安装pybloom-live 需要先安装 bitarray-0.8.3-cp36-cp36m-win_amd64.whl

其中 cp36为 python3.6 版本。 amd64为操作系统64位

下载地址：https://www.lfd.uci.edu/~gohlke/pythonlibs/#bitarray

下载好之后再本地安装:

 

库的使用

该模块分为两个类：

BloomFilter：指定容器大小

ScalableBloomFilter：可以自动扩展容器大小。

模块结构：

 

简单例子：

 

查看结构：

 

 

至于其它事项，可去查看源码。里面都写得很清楚。。。