位图的概念

在说布隆过滤器之前还是讲讲位图，BitMap，这个东西，先来回答这么一个问题，如果这个时候你需要判断一个整数是否在一堆整数当中，你会使用什么数据结构？散列表吗？这个当然是可行的，但是好不好呢？

这里我的问题是只需要判断一个数在不在这一堆数里面，注意这里我要的结果其实只有两个，“在” 和 “不在”，如果说用散列把这些实际的数字全部存起来显然不是最理想的做法，我们只需要标记这个些数字存在即可，你可能会想到用 boolean 数组来做存储，还能不能继续优化？既然是 Binary 问题，那么一个 bit 是不是就够了，0 用来表示 false，1 用来表示 true，一个整数 4 个字节，32 bits，我们用一个 bit 就解决了，这样我们就把存储空间缩小了 32 倍。

这个就是位图的概念，其就是用 bit 来作为存储数据的单位，数据量小的话，其优势可能并不明显，但是对于海量数据优势就很明显了。

BitMap 其实就是一个整型数组，你也可以把其想象成 n * 32 的二维 bit 数组，但是这里还是有一个问题，上面我们讨论的仅仅是针对整数的存储是这样子，现实生活中，我们常常接触的会是字符串这类的数据，那这个该如何存储，我们该如何从字符串对应到实际的数组 index，这就要说到布隆过滤器了。