前言

鱼和熊掌不可兼得的道理在计算机的世界中普遍适用，我们在设计程序时，总是需要做各种各样的取舍平衡（trade-off），比如用空间换时间，又或者用时间来换空间。
而从HashSet到布隆过滤器，则是时间/空间和程序精准度的一个平衡取舍。

1. 传统的HashSet

需求：判断一个元素是否在一个集合中。

传统HashSet中（以字符串为例）：

1. 添加：通过字符串的hash值，快速定位到基准位置，hash冲突时，进行冲突处理，然后插入；
2. 查找：通过字符串的hash值，快速定位到基准位置，在基准位置开始查找，直至找到字符均匹配的元素。

当HashSet基于字符串数组、hash冲突解决方案为线性探查法（冲突就找下一个位置）时：

HashSet插入 HashSet查找

传统HashSet是百分百精准的（之前插入过的一定能找到，没插入的一定找不到）。对于少量数据，HashSet非常方便实用；然而当数据量极其庞大时，无论空间还是时间的消耗，可能都达到了一个不可接受的量级。

2. 不精准的HashSet

事实上，如果只是为了【判断一个元素是否在一个集合中】，且允许存在一定的误判几率的话，我们大可不必记录原始数据，只需要和其生成的hash打交道即可。具体的做法可以为：
不再保存源数据（字符串），而是使用boolean数组，简单记录哪些元素(hash)是已存在于集合中的：

不精准的HashSet

虽然空间省了（String[ ] ⇒ boolean[ ]），效率也提升了（不用管hash冲突），但副作用也来了：未曾插入过集合的“赵六”也被判定为“存在”了。

我们可以通过一些方法降低误判率：

1. 增大数组长度
   比如上面数组长度从5增加到20时，hash=1/6/11落到了index=1/6/11的位置，自然不会冲突了：
   
2. 添加新的hash函数
   比如新增一个hash2函数，“张三”的 [hash1=1, hash2=2]，“赵六”的[hash1=11, hash2=4]；
   插入“张三”时，数组中index=1/2的标记均置为true，查询时也必须两个均为true，才认为是查找成功；
   因为“赵六” 对应的index=1/4，没有全部为true，则认为查找失败：
   

我们可以根据集合中的数据量以及容忍的误判率，从而选择合适的数组长度及hash个数。

3. 布隆过滤器

3.1 基于bit的布隆过滤器

1个boolean需要占用1个字节(8bit)，然而标识【存在/不存在】这两种状态，只需1bit即可：1=存在，0=不存在：

基于bit的布隆过滤器

现代编程语言没有直接提供 "bit"这样的基本数据类型，不过我们可以使用byte/int/long等进行替换，只是位置定位的方法需要简单地改变一下。以byte(8bit)为例，先确定在数组中的位置、然后确定bit在byte中的位置（通常是从低位到高位）：

基于byte的布隆过滤器

上图其实就是布隆过滤器的全貌了，当然，我们可以通过新增hash函数个数降低误判率：

多个Hash的布隆过滤器

查找的过程和boolean类似，对应位置的bit均为1时认为查询成功：

布隆过滤器查询

---

像以上通过将源数据映射为1bit，用于表示 [真/假]、[有/无]、[存在/不存在] 等两种状态，从而达到压缩空间的方法称之为BitMap算法，与之对应的数据结构通常被称之为BitSet（参考Java/C++的API）

比如我们需要记录 0-7共八个数字是否在集合中，我们只需要8bit(1个字节)即可：0在 则[0 0 0 0, 0 0 0 1]，1在 则[0 0 0 0, 0 0 1 0]，0和1都在 则 [0 0 0 0, 0 0 1 1]；全部数字都在，则为 [1 1 1 1, 1 1 1 1]。当新增第九个数字8时，BitSet则需要扩容为两个字节了。针对数字是否在集合中这一判断，BitMap是准确的，因为它总是不断扩容以满足需求。

在布隆过滤器的运用中，BitSet中记录的是hash值，准确说应该是[hash % 数组长度] 的值（因为数组长度固定）；
因为[原数据 ⇒ hash]是多对1的，[hash ⇒ index]也是多对一的，所以布隆过滤器依然是存在误差的。

3.2 数组长度和函数个数的确定

实际运用中，我们可以根据集合中需要插入的【存量数据量n个】、【容忍的误判几率p】，从而推导出合理的【数组的长度m(bit)】和【hash函数个数k】，公式可以参考：

比如现在有1000万个IP黑名单，别人访问网站时，需要判断是否这个人在黑名单内，如果在则拒绝访问。
我们允许误判达到万分之一，此时 n=10 000 000，p=0.0001，套公式=>
m = -10 000 000 * ln(0.0001) / (ln2)^2 ≈ 1.9 * 10^8 bit ≈ 22.85MB
k = (1.9 * 10^8) * ln2 / 10 000 000 ≈ 13 个
我们只需要使用22.86MB的内存+13个hash函数即可完成任务。

关于N个hash函数的选择，可以参考谷歌Guava中的做法：
hash1 = hash(原始数据)，这里的hash算法可以为 MurmurHash或MD5等
hash2 = hash1 + 1 * hash1>>>32
hash3 = hash1 + 2 * hash1>>>32
...
hashN = hash1 + (N-1) * hash1 >>> 32

3.3 布隆过滤器简单总结

作用：【检索一个元素是否在一个集合中】
优点：空间占用少、查询效率高；
缺点：存在误判 （不在集合中的元素也有可能被判定为“存在”）、删除困难。

关于删除困难：

1. 传统的布隆过滤器(1bit) 是不支持删除的，因为有可能多个数据共享同一个bit（都置为1），删除一个数据时，如果直接置0，会影响其他数据的判断。
2. 可以使用计数支持删除操作，原理是将原来的1bit拓展为N-bit作为计数空间，新增时加1，删除时减1；相应地，总的空间大小会膨胀至原来的N倍；另外计数时需要考虑溢出N-bit的情况。