布隆过滤器，幼儿园话介绍

功能

• 迅速判断某个元素是否在一个集合当中
• 可能存在误判，即认为一个元素存在集合当中但是实际上并没有
• 如果认定某一个元素不存在集合中，那就一定不存在

使用场景

• 垃圾邮件识别
• 检测单词是否拼写正确
• 网络爬虫中一个网址是否已经被读取过

实现原理

• 首先需要一个 位集，多个 hash函数

• 把集合中的所有值都去执行全部的 hash 函数，然后把结果作为位集的下标，将位集在该处的值设置为 1

• 判断某个元素是否在集合中

  • 也用该元素去执行所有的 hash 函数结果值作为位集下标
  • 如果在位集中取出来全为 1 则说明该元素非常有可能在集合中

  图中的 x，y，z 即是当前集合，他们分别被映射了 3 个位置
  w 是待查找元素，通过映射后也得到三个位置，但是发现其中一个位置的值为 0，所以能确定 w 一定不存在集合当中