作用
用于判断某个元素是否存在于集合中
常规思路：
- 数组
- 链表
- 平衡二叉树
- 红黑树
- 哈希表
上述数据结构效率依次增高，但需要消耗大量内存。
布隆过滤器（Bloom Filter）介绍
布隆过滤器的实现基础是哈希函数，不同于哈希表的精确查找，布隆过滤器牺牲了准确性，它存在一定概率的误判。牺牲准确性来换取内存空间。
布隆过滤器的核心实现是一个超大的默认值为0的位数组和多个哈希函数
image
添加元素
- 将元素传入多个哈希函数
- 得到每个哈希函数返回的位数组位置
- 将这些位置的值值为1
查询元素
- 将元素传入多个哈希函数
- 得到每个哈希函数返回的位数组位置
- 如果该位置存在任一一个值为0，则该元素不存在，否则存在
常见应用场景
- 检查单词拼写
- 检测海量的名单
- 垃圾邮件过滤
- 爬虫中检测是否爬过某URL
