使用布隆过滤器用于Python网络爬虫URL去重 _布隆过滤器

【使用布隆过滤器用于Python网络爬虫URL去重】布隆过滤器（BloomFilter）类似于hash set，用来判断元素是否在集合中。但是与hash set区别是：布隆过滤器不需要存储元素值，就能判断元素是否在集合中。
说一下布隆过滤器优缺点：

布隆过滤器原理布隆过滤器是由一个特定长度的二进制向量（可以理解为位数组，如32位的位数组，大小为4个字节，每一位取值只有0和1）和多个哈希函数构成。
布隆过滤器添加元素过程：

文章插图

布隆过滤器查询元素过程：

如何判断字符串存在呢？
只需将字符串经hash(1,str)…hash(k,str)哈希映射，检查每一个映射所对应位数组位置的值是否都为1，若k个位置的值都是1，则字符串存在，不全为1，则字符串一定不存在。

其中选择k个哈希函数比较麻烦，这里换个思路，选择一个哈希函数，附带k个不同的参数

布隆过滤器参数选择布隆过滤器参数选择分为：哈希函数选择以及参数m,n,k取值
哈希函数选择
哈希函数的选择对布隆过滤器的性能影响很大，哈希函数要具有较好的离散性（能近似等概率的将字符串映射到各个位）。
哈希函数推荐采用Murmur hash

Murmur hash是一种非加密型哈希函数，适用于一般的哈希检索操作，与其它流行的哈希函数相比，对于规律性较强的字符串内容，MurmurHash的随机分布特征表现更良好，而且计算性能也很快

参数m,n,k取值

当k、m、n三者满足 k = ln(2)* m/n 时，误识别率最低。

当哈希函数个数k=10，位数组长度m是字符串个数n的20倍时，误识别概率是0.0000889 ；即10万次判断，存在9次误判，1亿次判断，误判的次数为9000次

布隆过滤器应用

使用布隆过滤器用于Python网络爬虫URL去重