布隆过滤器
布隆过滤器用于判断元素是否在一个集合中。布隆过滤器的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。布隆过滤器只能判断值可能在集合中，或是一定不在集合 中。
实现
布隆过滤器本质是长度为 m 的位列表，存入的值只能为0或1。
当加入一个元素 i 时，使用 k 个不同的哈希函数对 i 进行哈希计算，得到 k 个不同的哈希值。在二进制列表中将这 k 个哈希值对应的位置标记为1。如果这k个位置中已经有值为1，则表示该值可能在集合中，否则该值一定不在集合中。
为什么要使用多个哈希函数
如果只使用一个哈希函数，将会存在大量的空间浪费。
应用
- 在 redis 中可用于解决缓存穿透问题；
- 网页爬虫对 URL 去重，避免爬取相同的 URL 地址；
- 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；
- Google Chrome 使用布隆过滤器识别恶意 URL；
- Medium 使用布隆过滤器避免推荐给用户已经读过的文章。