详解布隆过滤器及其模拟实现

布隆过滤器

引入

概念

工作原理

模拟实现布隆过滤器

哈希函数集

布隆过滤器基本框架

add函数（添加到布隆过滤器中）

contains函数（判断是否存在该值）

完整代码

布隆过滤器的删除

布隆过滤器的误判率

布隆过滤器的优点

布隆过滤器的缺点

布隆过滤器的应用场景

布隆过滤器

引入

我们如何判断一个元素是否在一个集合中？

我们可能会想到将集合中所有的元素加载到内存中，并存储到哈希表中，这样就能很容易判断出一个元素是否在一个集合中，但是这只能处理集合元素数量并不大的场景，对于集合中有海量的元素时，是行不通的，那么该如何解决呢？

我们知道，使用哈希表来存储，优点是能够快速查找，缺点是浪费空间；使用位图来存储，优点是能够快速查找，也不浪费空间，但是缺点是一般只能处理整形，对于较复杂的内容就无法处理了。

将哈希表和位图相结合，得到了一种新的结构，即“布隆过滤器”，它能够解决掉上面的问题。

概念

布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，由Burton Howard Bloom在1970年提出。它主要用于判断一个元素是否可能属于某个集合，而不支持直接获取集合中的所有元素。布隆过滤器的基本结构是一个固定长度的位数组/位图（Bit Array）和一组哈希函数（Hash Functions）。它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

概念图：

工作原理

（1）初始时，位图中所有位置的值设置为0.

（2）当有值通过哈希函数映射到该位置时，值才置为1。

（3）通过判断某个值哈希映射得到的每个位置的值是否不为0，就能知道该值“一定不存在”或者“可能存在”。

模拟实现布隆过滤器

哈希函数集

class SimpleHash {public int cap;//当前容量public int seed;//随机public SimpleHash(int cap,int seed) {this.cap = cap;this.seed = seed;}//根据seed不同 创建不能的哈希函数int hash(String key) {int h;//(n - 1) & hashreturn (key == null) ? 0 : (seed * (cap-1)) & ((h = key.hashCode()) ^ (h >>> 16));}}

上面的哈希函数参照了HashMap的原码：

布隆过滤器基本框架

public class MyBloomFilter {public static final int DEFAULT_SIZE = 1 << 20;//位图public BitSet bitSet;public static final int[] seeds = {5,7,11,13,27,33};public SimpleHash[] simpleHashes;public MyBloomFilter() {bitSet = new BitSet(DEFAULT_SIZE);simpleHashes = new SimpleHash[seeds.length];for (int i = 0; i < simpleHashes.length; i++) {simpleHashes[i] = new SimpleHash(DEFAULT_SIZE,seeds[i]);}}
}

add函数（添加到布隆过滤器中）

将要添加的值使用若干哈希函数进行映射，并将映射位置的值置为1.

public void add(String val) {//让若干个哈希函数  分别处理当前的数据for (SimpleHash simpleHash : simpleHashes) {int index = simpleHash.hash(val);//把他们 都存储在位图当中即可bitSet.set(index);}
}

contains函数（判断是否存在该值）

将要添加的值使用若干哈希函数进行映射，并以此判断这些位置的值是否为0，若存在为0的情况，则该值一定不存在，否则，是可能存在，因为可能存在其他值映射到这些位置的情况。

public boolean contains(String val) {for (SimpleHash simpleHash : simpleHashes) {int index = simpleHash.hash(val);//只要有1个为 0     那么一定不存在boolean flg = bitSet.get(index);if(!flg) {return false;}}return true;
}

完整代码

import java.util.BitSet;class SimpleHash {public int cap;//当前容量public int seed;//随机public SimpleHash(int cap,int seed) {this.cap = cap;this.seed = seed;}//根据seed不同 创建不能的哈希函数int hash(String key) {int h;//(n - 1) & hashreturn (key == null) ? 0 : (seed * (cap-1)) & ((h = key.hashCode()) ^ (h >>> 16));}}
public class MyBloomFilter {public static final int DEFAULT_SIZE = 1 << 20;//位图public BitSet bitSet;public static final int[] seeds = {5,7,11,13,27,33};public SimpleHash[] simpleHashes;public MyBloomFilter() {bitSet = new BitSet(DEFAULT_SIZE);simpleHashes = new SimpleHash[seeds.length];for (int i = 0; i < simpleHashes.length; i++) {simpleHashes[i] = new SimpleHash(DEFAULT_SIZE,seeds[i]);}}public void add(String val) {//让若干个哈希函数  分别处理当前的数据for (SimpleHash simpleHash : simpleHashes) {int index = simpleHash.hash(val);//把他们 都存储在位图当中即可bitSet.set(index);}}public boolean contains(String val) {for (SimpleHash simpleHash : simpleHashes) {int index = simpleHash.hash(val);//只要有1个为 0     那么一定不存在boolean flg = bitSet.get(index);if(!flg) {return false;}}return true;}public static void main(String[] args) {MyBloomFilter myBloomFilter = new MyBloomFilter();myBloomFilter.add("hello");myBloomFilter.add("hello2");System.out.println(myBloomFilter.contains("hello"));System.out.println(myBloomFilter.contains("hello3"));}
}

运行结果：

布隆过滤器的删除

布隆过滤器不支持直接删除，因为在删除一个元素时，可能会影响其它元素。

例如，通过上图可以看到，baidu和tencent有相同的映射位置，因此如果直接删除某个元素，可能会影响到其它元素。

那么有没有办法使得布隆过滤器支持删除操作呢？

有，比如给每个比特位附带一个计数器，当有元素映射到该位置时，该位置的计数器进行++，当删除元素时，只需要将对应位置的计数器进行- -。

缺陷：

1.无法确认元素是否真的在布隆过滤器中，即可能会判断失误。

2.存在计数回绕，即溢出。

布隆过滤器的误判率

n：布隆过滤器最大处理的元素的个数
P：希望的误差率
m：布隆过滤器的bit位数目
k：哈希函数的个数

布隆过滤器的优点

1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
2. 哈希函数相互之间没有关系，方便硬件并行运算
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

布隆过滤器的缺点

1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
2. 不能获取元素本身
3. 一般情况下不能从布隆过滤器中删除元素
4. 如果采用计数方式删除，可能会存在计数回绕问题

布隆过滤器的应用场景

1.缓存穿透防护：在分布式缓存系统如Redis或Memcached中，用于避免缓存穿透问题。当一个请求试图访问数据库中的某个不存在的键时，如果直接去数据库查询会增加数据库压力。通过在前端部署一个布隆过滤器，可以预先判断该键很可能不存在于数据库中，从而避免对数据库发起无效请求。
2.URL去重：在爬虫抓取网页或者日志分析中，用于URL去重，确保不会重复抓取相同的页面或记录。
3.大数据处理：在Hadoop等框架中，用来过滤掉重复的数据块或者记录，减少计算和存储负担。
4.垃圾邮件过滤：在电子邮件系统中，用于快速判断收到的邮件是否可能来自已知的垃圾邮件发送者。
5.异常事件检测：当大量事件流经系统时，可以用于快速识别并过滤出已知异常事件，降低报警系统误报率。
6.个性化推荐：在个性化推荐系统中，用于快速排除用户已经浏览过或者不感兴趣的内容。
数据库辅助索引：对于大型数据库，可以利用布隆过滤器作为辅助索引结构，提前过滤掉大部分肯定不在结果集中的查询条件，减轻主索引的压力。
7.内容检测：在社交网络中，用于快速检测用户上传的内容是否存在违规信息，或是检查用户ID、账号是否存在黑名单中。