应用场景
- 判断一个元素是否存在于一个集合中
- 字处理软件中，需要检查一个英语单词是否拼写正确
- 在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上
- 在网络爬虫里，一个网址是否被访问过
- yahoo, gmail等邮箱垃圾邮件过滤功能
优点：
- 空间效率高
- 查询效率高
缺点：
- 有误判的可能
原理
假设集合里面有3个元素{x, y, z}，哈希函数的个数为3。
首先将位数组进行初始化，将里面每个位都设置位0。
对于集合里面的每一个元素，将元素依次通过3个哈希函数进行映射，每次映射都会产生一个哈希值，这个值对应位数组上面的一个点，然后将位数组对应的位置标记为1。
查询W元素是否存在集合中的时候，同样的方法将W通过哈希映射到位数组上的3个点。
如果3个点的其中有一个点不为1，则可以判断该元素一定不存在集合中。
反之，如果3个点都为1，则该元素可能存在集合中。
注意：此处不能判断该元素是否一定存在集合中，可能存在一定的误判率。