在上次面试中，遇到了这样一个问题：

有两个文件，每个文件中都有10亿条数据，内存只有10M，求这两个文件中相同的数据，时间复杂度是多少？
如果其中一个文件只有100条数据，那么又是怎样呢？

当时看到这个题目的时候，我懵逼了。真的不知道为什么，那天做面试题我特别困，头也特别痛，没怎样想，最后就空着没做了。后来回去后睡了个午觉，这时突然就知道怎样做了。

• 初始想法
  在睡晚午觉后，我当时第一个想法就是，我把每个文件都都遍历以下，一条一条对比，把相同的数据写到另一个文件中，这样不就好了吗？
  如果真的是这样的做法，那时间复杂度又是多少呢？
  两个文件都遍历，在最差的情况下，对比每一条数据，我都需要把另外一个文件从头遍历到尾，那么时间复杂度就是 O(n²)。
  嗯~~~时间复杂度是不是有点夸张呢？我想面试官应该不会接受这样的答案吧？于是我有想了一下，突然想起了一个词——BitMap。没错了，应该用BitMap可以解决这道题。

什么是BitMap？

位图（Bitmap），又称栅格图（英语：Raster graphics）或点阵图，是使用像素阵列(Pixel-array/Dot-matrix点阵)来表示的图像。

上面是摘自百度百科的介绍。但其实，把BitMap翻译成位图感觉有些不太适当，如果把它叫位的映射图可能会更好地理解。
下面先看一个例子：
假如我们有这样一堆整数，每个整数都是int32类型的，如 [1,4,6,12]，我们可以怎样存储到内存中呢？

• 方法一：
  最直接的方法，就是把数据直接存进去就是了，所以，内存中存储的数据大概是长这个样子的

[0000 0000 0000 0000 0000 0000 0000 0001,  # 1
 0000 0000 0000 0000 0000 0000 0000 0100,  # 4
 0000 0000 0000 0000 0000 0000 0000 0110,  # 6
 0000 0000 0000 0000 0000 0000 0000 1100]  # 12

如果我们忽略掉数组这样的结构所耗费的空间，那么这4个整数所消耗的空间应该就是 32bit * 4 = 128bit = 16byte。所以4个整数需要用16个字节。
当然，数据量少可以这么做，但是当数据量大到一定程度，比如说有10亿个数，那么需要多少空间呢？
一个数就是4个字节，10亿个数就是：
10亿 * 4byte = 40亿 (byte) = 40亿 (byte) / 1024 (KB) / 1024 (MB) / 1024 (GB) ≈ 3.73GB
10亿个数需要3.73GB，真的没点内存也搞不掂这么多数据，更何况2组10亿呢？

• 方法二：
  我们换个思维，如果仅仅只是对这些数据进行存储，我们可以假设这样的一个对应关系。
  在内存中，我们假设每一个bit的位置対映一个数字，比如说：

每一个bit対映一个数

从上图看，我们假定最后边的第一个bit位対映0这个数字，第二个bit位対映1这个数字，如此类推。如果那个数存在，那么就在它对应的位置上的值设为1，我们只用8bit的空间就存储了 [1,2,4,6] 这4个数了。
由于题目给定的这一堆整数我们并不知道最大值是什么，但我们知道它是每个数都是int32类型，所以这一堆数的值范围应该是 -2³¹ ~ 2³¹-1，所以应该有 2³² 这么多种可能。为了应付每一个数字我都能找到它们的対映关系，所以我们必须申请这么多空间：
2³² Bit = 2³² (Bit) / 8 (Byte) / 1024 (KB) / 1024 (M) = 512M
看到这里的同学可能有一点疑惑？我数据都还没存咧，这么快就需要512M的空间了吗？
对，没错，在还没存数据之前，我们就首先把需要用到的空间申请下来，保证不会漏掉某个数。
其实这里也看到了BitMap的一个问题，就是数据稀疏。如果数据量少的情况下，我们使用bitmap进行排序、去重等操作，其实很多位置都是浪费的。
但是当数据量大的情况下使用bitmap，不管是10亿条数据还是多少条，我都能用这512M的空间给你存放进来。

Bit-map的基本思想就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。（PS：划重点 ）

BitMap的实现

由于我们不可能一次性拿到512M这样一片连续的内存空间，并且即使拿到了，管理起来也不太方便，因此，通常的，我们会申请多块内存，并且使用一个数组保存起来。这就是为什么我们通常看别人代码实现的bitmap都使用数组的原因（仅个人理解）。
至于数组中里每个位置的值，是int8、int16、int32还是int64，那就取决于你想用哪个了。加入我们这里使用int8，于是，就有了这样的一个数据结构：

[0x00000000, 0x00000000, 0x00000000, 0x00000000, .......]

如果我们添加1到这个bitmap中，那么上面的数组就应该变成下面的样子：

[0x00000010, 0x00000000, 0x00000000, 0x00000000, .......]

添加12到这个bitmap中，那就应该是：

[0x00000010, 0x00010000, 0x00000000, 0x00000000, .......]

所以，如果要在这一的结构中定位到某个数n的位置，应该是这样的计算

数组中的索引
index = n // 8
该索引中的第几位的值
set = n % 8

由于作者太懒了，具体的代码实现方式请参考https://www.cnblogs.com/myseries/p/10880641.html

BitMap的应用

一、对大量数据进行去重

基于bitmap的特性，可以使用bitmap对大量的数据进行去重

二、有两组40亿的整数，分别求出这两组数的交集和并集

构建两个BitMap，直接进行按位与和按位或操作。这样只需要512M*2的空间。也是可以接受的。

三、使用bitmap进行排序

对于一组不存在重复数据的数据中，可以使用bitmap进行排序，由于位运算的高效性，所以时间复杂度是 O(N)

四、快速查询

对一个已有的bitmap数据，可以快速计算其数所在的下标，并且求余可以知道该数的位置，这样就能够查看是否有该值

五、给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url?

这里需要使用 hash+分治思想，具体请参考https://www.pianshen.com/article/24931746611/

---

参考：
https://www.pianshen.com/article/24931746611/
https://www.cnblogs.com/cjsblog/p/11613708.html
https://www.cnblogs.com/myseries/p/10880641.html