海量数据存储与查询之布隆过滤器_布隆过滤器最多可以保存多少数据

提出问题

1. 如何快速在亿级黑名单中快速定位URL地址是否在黑名单中？（每条URL平均64字节）
2. 目前有十亿数量的自然数，乱序排列，需要对其进行排序，在32位机器上完成，内存限制2G

---

如何存储海量数据

• 链表：O(1)的插入删除，O(n)的查找速度，由于过慢的查找速度所以不适合。
• 散列表（hashmap）：数组+链表/红黑树，具有优秀的查找速度。但是经过计算，一亿的int需要花费12GB+，因此全部无法放入内存中，不适合。

假设存放1，3，5，7四个数字，存放在数组中需要花费16字节(Byte)
这里考虑用位图的方式，初始化一个bit[8]的数组，数组由8个8bit组成，将1，3，5，7对应位置位1，此时，利用这1字节的空间就可以存放8个数字，内存消耗相当于原来的1/32.

位图，适合存储大数据，每一位代表一种状态

• 位图的优势：对位图进行遍历，出来的数据自带排序效果，同时方便去重
• 位图的缺点：数组下标只有数字，有限制；空间利用率低。（即保存1和1亿两个数，此时位图远比8字节大得多）

如何解决缺点呢？利用哈希函数机制来进行映射。（布隆过滤器）

---

布隆过滤器

---

注意布隆过滤器的误差机制（由于哈希碰撞导致）

哈希函数越多，误判率越低（空间足够的情况下），但是运行时消耗的计算时间会增加。
若空间不足，则会导致误判率接近1，即空间已满，无论用多少哈希函数都不能正确判断

布隆过滤器总结：判断存在的时候不一定存在，但是判断不存在的一定不存在
布隆过滤器适合用在对数据很少删除，且无需精确确定是否存在的业务场景

---

使用场景

布隆过滤器的最大的用处就是，能够迅速判断一个元素是否在一个集合中。因此它有如下三个使用场景:

• 网页爬虫对 URL 的去重，避免爬取相同的 URL 地址
• 进行垃圾邮件过滤：反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱（同理，垃圾短信）
• 有的黑客为了让服务宕机，他们会构建大量不存在于缓存中的 key 向服务器发起请求，在数据量足够大的情况下，频繁的数据库查询可能导致 DB 挂掉。布隆过滤器很好的解决了缓存击穿的问题。