1. 什么是位图
- 前面介绍了哈希算法，同时也指出了哈希算法存在的空间复杂度太高问题，那么有没有一种数据结构满足 既能处理大量数据，同时又不占用太多空间 的要求呢？
- 这里我们介绍另一种叫 位图 的数据结构，这里的位图并不真的是图，而是按照集合中最大元素 max 创建一个长度为 max+1 的新数组，在数据存入时扫描原始数组，每当遇到一个数值就把新数组该位置写为 1，比如遇到 5 就给新数组的第 6 个元素置 1，这样下次再遇到 5 时发现新数组的第 6 个元素已经是 1 了，这说明这次的数据肯定和以前的数据存在着重复。这种给新数组 初始化时置零其后置一的做法，类似于位图的处理方法故称 位图算法；
- 这段定义文字可能看起来很拗口，我们解读一下他的含义，位图算法的作用是可以用一个 数据位 来存放一种状态（比如 1 和 0），如果我们想知道某个数值是否已经存在，我们只需要找到对应的数据位查看该数据为的状态即可；
2. 位图算法的实现
- 假设我们有一个数组 {1,3,7}，我们需要设计一种方法来存储它，有什么方法可以佣金可能小的内存空间把它存储下来呢？
- 我们可以使用使用一个 8 位的地址空间，在从 0 到 7 这 8 个位上，我们按顺序将数值对应的位的值置为 1，得到的结果就是 01010001，如下图所示：
- 在这样一个 8 位的地址空间上，我们存储了 3 个 0 到 8 之间的数字；
- 那么我们如果想存储的数字介于 0 到 15 之间呢，比如 {1, 2, 5, 7, 11}，其实解决问题的方法和上面是一样的，只不过用于存储的空间需要更长，这里我们申请一个 16 位的地址空间，然后根据位置对应的值依次重置数值；
- 位图最典型的应用，是在一段已知长度的地址空间中，用二进制方式（即 1 和 0）存储数据的状态，而一个数只有存在和不存在两个状态，这里的 1 代表存在，0 代表不存在，当我们查询的时候只需要知道目标位置上是 1 还是 0；
- 当有有多个值需要进行复杂的查询的时候，我们只需要对二进制数组进行 位运算，就可以很快找到我们想要的结果，这也是算法被称为 位图 的原因；
关于位图算法，有一篇很经典的文章，是由 程序员小灰 所写的《漫画：什么是Bitmap算法？》，建议读者朋友去读一读，看完以后对于位图算法的实现和应用将有更加清晰的认识。
3. 512M 内存查找 43 亿数据
- 关于位图算法，网上的文章中经常会讲到这个例子，这个例子同时 BAT 的经典算法题之一，我们也用这个例子做个讲解；
- 假设我们现在有 43 条数据，需要判断一个数据是否已经出现过，如果已经出现就丢弃，否则就作为新数据添加到 43 亿条数据中，我们该如何实现这个需求呢？
- 构建数组
- 首先，我们需要注意 43 亿这个数字，接触过 32 位系统知识的读者可能已经注意到，2 的 32 次方 等于4294967296，约等于这里的 43 亿；
- 结合前面的位图算法相关知识，我们在这里申请一个 32 位的数组，初始状态下每个位都置 0，表示该位上为空（没有数值），当我们拿到一个数字，我们就到对应的位上把值置为 1，表示此位上对应的数值已经被添加；
- 按照上面的顺序类推，我们就构建了一个容量为 43 亿的数组，在这个数组中最大可以存储 43 亿个数值的状态；
- 查找数据
- 当我们拿到一个新的数值的时候，我们只需要到对应的位上查看该位状态值是否为 1，就知道是否已经存在该数值；
- 内存使用情况
- 分析下内存空间，我们申请了 32 位的内存，每个位上只有 1 和 0 两种状态，总计 2 的 32 次方个位的空间，就是 2 的 29 次方个字节，就相当于 500MB；
- 这样，我们就解决了 512M 内存查找 43 亿数据的问题，而解决问题的思路其实就是 位图 算法的思想。
4. 位图算法的应用
-
位图算法适用于数据量很大但数据状态又不是很多的情况，通常是用来判断某个数据存不存在的；
- 具体应用：
- 快速查找某个数据是否在一个集合中；
- 排序；
- 求两个集合的交集、并集等；
- 操作系统中磁盘块标记；
- 在这里我们就不对这些具体应用展开来讲了，感兴趣的朋友可以自行百度谷歌了解相关知识。
5. 位图算法处理不了哈希冲突
- 前面讲的位图算法的内容，都是围绕 数值 展开的，但实际业务场景下要处理的对象很少严格意义的数值，最常见的处理对象其实是 字符串，那么我们该怎样将字符串映射
- 有些人应该想到了，就是我们前面讲的哈希，使用一个哈希函数将字符串对象映到一个数组的位置上，比如我们拿到一个 url 以后，代入哈希函数得到一个数值，然后通过位图算法在数
- 位图更节省空间，但因为处理不了哈希冲突，所以仍不能满足业务需求；
