布隆过滤器

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1. 前言 笔者早几年的工作经历和爬虫相关，为防止重复抓取URL, 要对每个需要抓取的URL进行判重，由于每天待抓取的URL数量都在好几亿条。因此去重服务的压力很大，当时相关的小伙伴就曾经调研过布隆过滤器。 本文笔者将结合Google Guava的BloomFilter(com.google.common.hash.BloomFilter)，谈谈布隆过滤器的实现，以及它的一些特点。 2. 布隆过滤器简介 An empty Bloom filter is a bit array of m bits, all set to 0. There must also be k different hash functions defined, each of which maps or hashes some set element to one of the m array positions, generating a uniform random distribution. 布隆过滤器由一个m位的bitArray以及k个hash函数组成。m和k的具体值可以由布隆过滤器中预期存储的数据量n，以及可能出现假阳性概率p决定。 待存储的数据经过1个hash函数作用，并会将bitArray中的某一位置成1 k个hash函数最多会将bitArray中k位置成1 如上图所示,假定k=2 hash_func1将bitArray[3]=1 hash_func2将bitArray[8]=1 如果想判断数值1990是否在布隆过滤器中，只需要重新执行hash_func1和hash_func2，如果第3位和第8位都是1，那么1990可能在布隆过滤器中(存在假阳性的可能)，反之第3位和第8位有1位为0，则1990一定不在布隆过滤器中。 可以换一个角度来解释布隆过滤器，每个hash函数都在尝试提取数据值的一部分特征。存储数据的过程(置1)，实际是在标记，布隆过滤器中至少包含一个元素满足特定的特征。如果有一个特征不满足，那么该数据一定不在布隆过滤器中。 ...