详解布隆过滤器+scrapyredis持久化去重_k个不同的哈希函数

前提

网上大部分python实现的布隆过滤器库如：pybloomfilter、pybloom 但都是基于py2且哈希函数用的都是sha1类、md5类，效率不如mmh3.所以决定自己实现，

git地址：https://github.com/Sssmeb/BloomFilter

第一次自己实现库 求星星！！ 也欢迎讨论、指教！！

Bloom Filter（布隆过滤器）

布隆过滤器是一种多哈希函数映射的快速查找算法，通常应用在一些需要快速判断某个元素是否属于集合，但并不严格要求100%正确的场合。

本质上是一种数据结构，比较巧妙的概率型数据结构。

布隆过滤器可能会出现误判，但不会漏判。即，如果过滤器判断该元素不在集合中，则元素一定不在集合中，但如果过滤器判断该元素在集合中，有一定的概率判断错误（在合适的参数情况下，误判率可以降低到0.000级别甚至更低）。

因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter相比于其他常见的算法极大节省了空间（相较于直接存储，可节省上千倍的空间）。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是存在误识别率和删除困难。

应用

常见适用的场景主要利用布隆过滤器减少磁盘io或网络请求等：

1. 黑名单
   • 例如 邮件黑名单过滤器，判断邮件地址是否存在黑名单中
2. 网络爬虫去重
3. K-V系统快速判断某个key是否存在
   • 例如 Hbase每个Region都包含一个BloomFilter，用于快速判断某个key在该region中是否存在
4. 缓解缓存穿透
   • 大量查询不存在数据的请求，越过redis缓存后，全部打到数据库中
   • 可以在服务器内存中搭建一个布隆过滤器缓解

去重背景

一般将数据存储用做去重判断的方法有：

1. 将数据直接存储到数据库中
2. 用HashSet（字典结构）/redis的set 将数据存储起来，实现O(1)时间复杂度的查询
3. 经过MD5 或 SHA-1等 单向哈希后再保存到HashSet或数据库
4. Bit-Map。建立一个BitSet，将每份数据通过哈希函数映射到某一位（bit）。

当数据量较小时，前3种方法都是不错的选择。但是当数据量非常大时（几G、甚至几十G）会出现存储瓶颈。

当数据量较大时，上述四种方法的表现：

1. 查询效率非常低，每检查一个数据是否存在时都需要扫描全表。
2. 占用大量的内存空间（内存较昂贵）
3. 由于字符串经过MD5或SHA-1处理后，长度只有128bit或160bit，所以当数据本身长度较大时，比方法2节省内存。
4. 消耗内存少，但单一哈希函数发生冲突的概率太高。若要冲突率降到1%，就要将Bitset的长度设置为数据个数的100倍。

Bloom Filter原理

基于以上的背景，可以看到：当数据量非常大时，方法4是较好的选择。但该较大的问题是冲突率高，为了降低冲突，Bloom Filter使用多个哈希函数，而不是一个。

总结BloomFilter的核心思想：

1. 多个hash，增大随机性，减少hash碰撞的概率
2. 扩大数组范围，使hash值均匀分布，进一步减少hash碰撞的概率

算法实现

1. 创建一个m位的BitSet，先将所有位初始化为0
   

2. 插入数据流程：

   1. 加入字符串，经过k个哈希函数，分别计算出k个范围是0 - m-1的值
   2. 将k个值对应的BitSet位 置1