理解布隆过滤器算法的实现原理

过滤器是「一种空间高效概率性的数据结构」(百科中原文是a space-efficient probabilistic data structure)，该数据结构于1970年由Burton Howard Bloom提出，「作用是测试一个元素是否某个集合的一个成员」。布隆过滤器是可能出现false positive(这个是专有名词"假阳性"，可以理解为误判的情况，下文如果用到这个名词会保留英文单词使用)匹配的，换言之，布隆过滤器在使用的时候有可能返回结果"可能存在于集合中"或者"必定不存在于集合中"。

布隆过滤器算法描述

在场景复杂的网络爬虫中，爬取到的网页URL依赖有可能成环，例如在URL-1页面中展示了URL-2，然后又在URL-2中的页面展示了URL-1，这个时候需要一种方案记录和判断历史访问过的URL。这个时候可能会想到下面的方案：

• 方案一：使用数据库存储已经访问过的URL，例如MySQL表中基于URL建立唯一索引或者使用Redis的SET数据类型
• 方案二：使用HashSet(其实这里不局限于HashSet，链表、树和散列表等数据结构都能满足)存储已经访问过的URL
• 方案三：基于方案一和方案二进行优化，存储URL的摘要，使用摘要算法如MD5、SHA-n算法针对URL字符串生成摘要
• 方案四：使用Hash函数处理对应的URL生成一个哈希码，再把哈希码通过一个映射函数映射到一个固定容量的BitSet中的某一个比特

对于方案一、方案二和方案三，在历史访问URL数据量极大的情况下，会消耗巨大的存储空间(磁盘或者内存)，对于方案四，如果URL有100亿个，那么要把冲突几率降低到1%，那么BitSet的容量需要设置为10000亿。

（编辑：张家口站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!