# Bloom Filter算法
Bloom filter是一种性能提升的手段，发明者为Burton Bloom。
布隆过滤器（Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
布隆过滤器类似于HashSet，区别在于布隆过滤器不需要保存key值（不需要保存set元素），因此其占用空间较少，具有安全性。
# 实现
创建一个Set的基本方式，我们可以使用hash函数，将每个元素映射为hash编码。布隆过滤器也是采用如下思想：
- 一个很长的二进制向量（位数组）。
- 一系列稀疏哈希函数。
布隆过滤器的思想是使用n个hash函数，使每个元素通过n次hash获得n个hash值，并在很长的二进制向量中标记对应位置。
# 添加元素
- 使用n个哈希函数计算出给定元素的n个映射值。
- 将二进制向量上n个位置置为1。
# 查找元素
- 使用n个哈希函数计算出给定元素的n个映射值。
- 在对应二进制向量上依次查找n个位置，如果均为1，则元素可能存在，只要有一个位置位0，则元素一定不存在。
# 复杂度与限制
布隆过滤器的查找复杂度为O(n)，n为哈希函数的数量。
正如hash的方式本身带来的问题一样，布隆过滤器计算hash时不同元素会存在hash冲突，因此即使查找元素时n个位置均为1，也可能存在误判。反过来，如果n个位置有0，那么可以肯定该元素一定不存在。
另一个限制是虽然布隆过滤器本质上是一个Set，但由于hash映射可能存在误判，因此删除元素的操作一般是禁止的（不然就错上加错）。
利用这一特点，可以做URL过滤，黑名单过滤等操作。