【数据结构】布隆过滤器 BoomFilter 的应用场景

阿里云国际版折扣https://www.yundadi.com

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

文章目录

前言

对比数据结构的区别从其空间、时间复杂度下手观察。BoomFilter 特殊的地方在于它在元素存储上做了努力。本文归纳下 BoomFilter 与 HashTable 的区别进而引出 BoomFilter 善于支持的应用场景。

1. 时间、空间复杂度

BoomFilter 与 HashTable 都用了hash函数对存储元素进行散列存储查找的时候都是 O(1) 的时间复杂度。二进制数组存储散列值两者都是 O(n) 的复杂度

2. BoomFilter 的取舍

BoomFilter 不会存储元素比如 “刘德华” 加入 BoomFilter 后会映射成为散列值。想用散列值还原 “刘德华” 则无法实现。这种取舍的效果

能让 BoomFilter 有比 HashTable 更少的元素存储空间 HashTable 会把 “刘德华” 存进数据结构
失去了根据 key 查找 value 的能力仅仅保留了 contains 的能力。

3. BoomFilter 能做什么

上文讲到 BoomFilter 保留了 contains 的能力其实是不准确的。
BoomFilter contains 能力简述

BoomFilter.contains(“刘德华”) == true => “刘德华” 可能在 元素集合中
BoomFilter.contains(“刘德华”) == false => “刘德华” 一定不在 元素集合中

具体原因可以看 [布隆过滤器BloomFilter] 举例说明+证明推导

综上BoomFilter 能够断定元素不存在集合中仅能推测元素可能在集合中存在误差但是不大。

4. BoomFilter 不能做什么

除了失去根据 key 查找 value 的能力BoomFilter 天然不支持删除功能。其原因是 BoomFilter 不处理哈希冲突。举一个例子

未映射元素的 BoomFilter 
[0, 0, 0, 0, 0]

加入刘德华

[0, 0, 0, 0, 0]
⬇
刘德华
⬇
hash映射为: [0, 1, 0, 0, 1]
⬇
加入 BoomFilter
⬇
[0, 1, 0, 0, 1]

加入张学友

[0, 1, 0, 0, 1]
⬇
张学友 (增量加入)
⬇
hash映射为: [0, 1, 0, 1, 0]
⬇
加入 BoomFilter (发生了hash冲突但是第二位的 "1" 不做处理)
⬇
[0, 1, 0, 1, 1]

删除张学友

[0, 1, 0, 0, 1]
⬇
张学友 (删除
⬇
hash映射为: [0, 1, 0, 1, 0]
⬇
踢出 BoomFilter 
⬇
[0, 0, 0, 1, 0]

删除张学友的同时破坏了刘德华的元素映射所以 BoomFilter 原生不支持删除操作

4.1 优化 BoomFilter

上文说到 BoomFilter 原生不支持删除操作是因为 BoomFilter 不处理hash冲突。如果为二进制数组中的每个 “1” 维护一个计数器就能标识hash冲突了。在删除元素的时候就不会把 “刘德华” 的 “1” 直接删除而是让计数器 -1。通过一个简单的计数器BoomFilter 又能支撑删除操作了。

5. BoomFilter 的误判及指导意义

[布隆过滤器BloomFilter] 举例说明+证明推导
这篇文章把误判率给推导出来了。我们可以得到一个结论当哈希函数个数不变时BoomFilter 中二进制“1” 的密度越大误判率越高。为了减少误判率

提前训练 BoomFilter
如果是白名单策略可以把系统所有白名单都加入到 BoomFilter 中在上线后尽量不维护元素。上线前根据 BoomFilter 的训练情况进行调参使得 “1” 的密度减少。
BoomFilter.contains(“刘德华”) == true 依旧要做兜底策略
只要存在误判的可能通过BoomFilter校验的元素依旧可能不是白名单要做权限控制或者服务降级的可能。